L'algorithme de Krukshal ou Prims Algorithm lequel est le meilleur dans la recherche de Spanning Tree minimum?

Question

Possible en double:
Kruskal vs Prim

algorithme de krukshal ou Prims algorithme qui est mieux pour trouver arbre minimum?

Answer 1

Je vais ajouter un point en faveur de l'algorithme de Prim que je n'ai pas vu mentionné. Si on vous donne N points et une fonction de distance d (x, y) pour la distance entre x et y, il est facile d'implémenter l'algorithme de Prim en utilisant l'espace O (N) (mais le temps N^2). Commencez avec un point arbitraire A et créez un tableau de taille N-1 en indiquant les distances entre A et tous les autres points. Choisissez le point B, associé à la distance la plus courte, lien A et B dans l'arbre recouvrant, puis mettez à jour les distances dans le tableau pour qu'elles correspondent au minimum de la distance déjà notée jusqu'à cet autre point et à la distance de B ot point, en notant où le lien le plus court est de B et d'où A. Continuer. Je ne connais pas une manière similaire de manipuler l'algorithme de Kruskal pour un graphe dense spécifié par une fonction de distance, et pour un grand N, vous pouvez manquer d'espace O (N^2) avant de manquer de patience pour le temps O (N^2).