Quand dois-je utiliser Kruskal par opposition à Prim (et vice versa)?

Je me demandais quand il faut utiliser L'algorithme de Prim et quand Kruskal de l' pour trouver le minimum spanning tree? Ils ont tous les deux facile logiques, même le pire des cas, et la seule différence est l'application qui pourrait impliquer un peu différentes structures de données. Alors, quel est le facteur décisif?

InformationsquelleAutor | 2009-07-28
  1. 190

    Utilisation de l'algorithme de Prim lorsque vous avez un graphique avec beaucoup d'arêtes.

    Pour un graphe avec V sommets E bords, de Kruskal algorithme s'exécute en O(E log V) du temps et de l'algorithme de Prim pouvez exécuter dans O(E + V log V) amorti temps, si vous utilisez un Tas De Fibonacci.

    De l'algorithme de Prim est nettement plus rapide dans la limite quand vous avez un très denses graphique avec beaucoup plus d'arêtes que de sommets. Kruskal fonctionne mieux dans des situations typiques (sparse graphiques) car il utilise plus simple des structures de données.

    • Je dirais "situations types" au lieu de la moyenne.. je pense que c'est un obscur terme à utiliser, par exemple, ce qu'est la "taille moyenne" d'une table de hachage? aucune idée.
    • N'oubliez pas d'ajouter que Prim est + des tas de Fibonacci donne un amorti temps de course, pas un scénario du pire temps d'exécution.
    • Je crois que vous êtes à comparer des pommes et des oranges. Amorti analyse est simpy une façon d'obtenir une mesure de la fonction (façon de parler) --- si c'est le pire des cas ou la moyenne des cas dépend de ce que vous êtes à prouver. En fait (comme je l'ai regarder jusqu'à maintenant), l'article de wiki utilise la langue qui implique que sa que utilisé pour l'analyse du pire scénario. Maintenant, en utilisant une telle analyse signifie que vous ne pouvez pas faire que de fortes promesses sur le coût d'une opération particulière, mais par le temps de l'algorithme est terminé, il sera en effet par O(E+VlogV), même dans le pire des cas.
    • Qui sonne bien en théorie, mais je parie que peu de gens peuvent mettre en œuvre un tas de Fibonacci
    • Qui doit mettre en œuvre un? Juste google pour une mise en œuvre existantes. Des tas de Fibonacci ont été autour depuis 1987.
    • il peut y avoir de C(V,2) les arêtes dans le pire des cas. Donc, n'a pas le temps compleixty de l'algorithme de Prim se résume à O(V^2 + VlogV) i.e. O(V^2) en cas de tas de fibonacci?
    • Il y a également un autre facteur important: la sortie de Prims est une MST seulement si le graphe est connecté (sortie me semble d'aucune utilité sinon), mais la Kruskal de sortie est le Minimum Couvrant les forêts (avec un peu d'utilisation).
    • vous pouvez modifier l'algorithme de prim légèrement pour obtenir une forêt sur un sans lien graphique. Tout ce que vous avez à faire est d'exécuter l'algorithme de tous les sommets de son bien expliqué dans le Princeton cours en ligne, algs4.cs.princeton.edu/43mst
    • Aussi, si maximal poids des arêtes est petit et discret (de préférence des entiers), alors vous pouvez seau bords de tri en temps linéaire, qui s'élève à O(E α(V)), où α est l'inverse de la fonction d'Ackermann (dans des cas pratiques, toujours moins de 5, puisque cette valeur n'est jamais obtenu par le nombre prévu d'atomes dans l'univers).

    InformationsquelleAutor Todd Gamblin
  2. 92

    J'ai trouvé un très beau sujet sur le net qui explique la différence d'une manière très simple : http://www.thestudentroom.co.uk/showthread.php?t=232168.

    Kruskal algorithme va croître une solution de la moins chère bord en ajoutant le côté le moins cher bord, à condition qu'il ne crée pas de cycle.

    De l'algorithme de Prim va croître d'une solution à partir d'un hasard vertex en ajoutant le côté le moins cher sommet, le sommet n'est pas actuellement dans la solution, mais auquel il est relié par le moins cher le bord.

    Ci-joint est intéressant de feuille sur le sujet.Quand dois-je utiliser Kruskal par opposition à Prim (et vice versa)?

    Si vous implémentez de Kruskal et de Prim, dans leur forme optimale : avec un syndicat trouver et un finbonacci tas respectivement, alors vous remarquerez combien de Kruskal est facile à mettre en œuvre par rapport à Prim.

    Prim est plus difficile avec un tas de fibonacci, principalement parce que vous avez à maintenir un livre de maintien de table pour enregistrer la bi-directionnelle lien entre les noeuds d'un graphe et tas de nœuds. Avec un Syndicat Trouver, c'est le contraire, la structure est simple et peut même produire directement le mst à presque aucun coût supplémentaire.

    • Pinailler: le Dernier "slide" dans chacun devrait lire "répétez jusqu'à ce que vous avez un spanning tree"; pas jusqu'à ce que la TMS, qui est quelque chose de récursive tâche - comment puis-je savoir que c'est minime, c'est pourquoi je suis Prim s/Kruskal pour commencer!
    • J'ai trouvé ce thread pour avoir cherché une illustration simple de Prim et algorithmes de Kruskal. Les algorithmes de garantie que vous trouverez un arbre, et l'arbre est une MST. Et vous savez que vous avez trouvé un arbre lorsque vous avez exactement V-1 bords.
    • Vous avez raison, en faisant le même point que mon commentaire précédent à partir d'un angle différent.
    • Mais n'est-il pas une condition préalable que vous avez seulement à choisir avec un seul poids entre les sommets, vous ne pouvez pas choisir de poids 2 plus d'une fois à partir du graphique ci-dessus, vous devez choisir la prochaine poids ex:3 @Snicolas
    InformationsquelleAutor Snicolas
  3. 27

    Je sais que vous n'avez pas demandé, mais si vous avez plus d'unités de traitement, vous devez toujours tenir compte de Borůvka de l'algorithme de, car il peut être facilement parallélisable - elle a donc un avantage de performance de plus de Kruskal et Jarník-algorithme de Prim.

    InformationsquelleAutor malejpavouk
  4. 21

    Kruskal peut avoir de meilleures performances si les bords peuvent être triés dans le temps linéaire, ou sont déjà triés.

    Prim est mieux si le nombre d'arêtes, de sommets est élevé.

    InformationsquelleAutor Daniel C. Sobral
  5. 15

    Si l'on arrête l'algorithme au moyen de l'algorithme de prim génère toujours connecté arbre, mais kruskal sur l'autre main peut donner déconnecté de l'arbre ou la forêt

    InformationsquelleAutor Prakhar
  6. 11

    Kruskal temps de la complexité pire cas est O(E log E),parce que nous avons besoin de trier les bords.
    Prim temps de la complexité pire cas est O(E log V) avec file d'attente de priorité ou encore mieux, O(E+V log V) avec Tas de Fibonacci.
    Nous devrions utiliser Kruskal quand le graphe est peu dense, je.e.petit nombre de bords,comme E=O(V),lorsque les bords sont déjà triés ou si nous pouvons faire le tri dans le temps linéaire.
    Nous devrions utiliser Prim quand le graphe est dense, je.e nombre d'arêtes est élevée ,comme E=O(V2).

    InformationsquelleAutor Ghiurutan Alexandru
  7. 5

    Une application importante de l'algorithme de Kruskal est dans seul lien de clustering.

    Envisager de n sommets et vous avez un graphe complet.Pour obtenir un k clusters de ces n points.Exécuter l'algorithme de Kruskal sur le premier n-(k-1) les bords de la triés ensemble d'arêtes.Vous obtenez k-cluster du graphique avec espacement maximal.

    InformationsquelleAutor Jaskaran
  8. 3

    Le meilleur moment pour Kruskal est O(E logV). Pour Prim est à l'aide de fib tas nous pouvons obtenir O(E+V lgV). Donc sur un dense graphique, Prim est beaucoup mieux.

    InformationsquelleAutor Leon Stenneth
  9. 2

    Prim est mieux pour plus denses graphes, et en cela, nous avons également ne pas avoir à payer beaucoup d'attention à la longueur des cycles de l'ajout d'un bord, comme nous sommes principalement affaire avec des nœuds. Prim est plus rapide que de Kruskal dans le cas de graphiques complexes.

    InformationsquelleAutor Sakshi
  10. 2

    De kruskal Algorithme nous avons nombre d'arêtes et le nombre de sommets d'un graphe, mais sur chaque bord, nous avons une certaine valeur ou le poids au nom de laquelle nous pouvons préparer un nouveau graphique qui ne doit pas être cyclique ou non à proximité de n'importe quel côté
    Par Exemple

    graphique comme ceci
    _____________
    | | |
    | | |
    |__________| |
    Donner le nom d'un sommet quelconque a,b,c,d,e,f .

    InformationsquelleAutor Abhishek