Wann sollte ich verwenden Kruskal als Gegensatz zu Prim (und Umgekehrt)?
Wurde ich gefragt, Wann sollte man Sie nutzen Prim ' s Algorithmus und wenn Kruskal ' s zu finden, die minimum-spanning-tree? Beide haben einfache Logik, gleich den schlimmsten Fällen, und der einzige Unterschied ist die Umsetzung, die könnte mit ein bisschen unterschiedlichen Datenstrukturen. Was ist also der entscheidende Faktor?
Du musst angemeldet sein, um einen Kommentar abzugeben.
Verwenden Sie Prim ' s Algorithmus, wenn man einen Graphen mit vielen Kanten.
Für einen Graphen mit V Eckpunkte E Kanten, die Kruskal-Algorithmus läuft in O(E log V) Zeit und Prim ' s Algorithmus kann im O(E + V log V) fortgeführten Zeit, wenn Sie eine Fibonacci-Heap.
Prim ' s Algorithmus ist wesentlich schneller die Grenze, wenn du hast eine wirklich Dichte Graphen mit vielen Kanten als Ecken. Kruskal eine bessere Leistung in typischen Situationen (sparse graphs), da Sie einfacher Daten-Strukturen.
O(E α(V))
, woα
ist die inverse Ackermann-Funktion (in praktischen Fällen immer weniger als 5, da dieser Wert nie erhalten von vorhergesagten Anzahl der Atome im Universum).Fand ich einen sehr schönen thread im Netz, erklärt den Unterschied in einer sehr einfachen Art und Weise : http://www.thestudentroom.co.uk/showthread.php?t=232168.
Kruskal ' s Algorithmus wird wachsen, die eine Lösung von der billigsten Kante, indem die nächste billigste Kante, vorausgesetzt, dass es nicht einen Kreislauf.
Prim ' s Algorithmus wird wachsen, eine Lösung von einem beliebigen vertex, indem die nächste billigste vertex, vertex gegenwärtig nicht die Lösung, aber verbunden mit den billigsten Kante.
Hier angebracht ist, ein Interessantes Blatt zu diesem Thema.
Wenn Euch die Umsetzung Kruskal und Prim, in Ihrer besten form : mit einer union zu finden und ein finbonacci heap jeweils, dann werden Sie merken, wie Kruskal ist einfach zu implementieren im Vergleich zu Prim.
Prim ist schwieriger, mit einem fibonacci-heap-vor allem, weil Sie haben, pflegen eine Buchhaltung Tabelle zum aufzeichnen der bidirektionalen link zwischen Knoten des Graphen und heap-Knoten. Mit einer Union zu Finden, im Gegenteil, die Struktur ist einfach und kann sogar zu produzieren, die direkt die mst, fast ohne zusätzliche Kosten.
V-1
Kanten.Ich weiß, dass Sie nicht Fragen, für diese, aber wenn Sie haben mehr Verarbeitungseinheiten, sollten Sie immer prüfen,Borůvka-Algorithmus, denn es könnte leicht parallelisiert, daher hat es einen performance-Vorteil gegenüber Kruskal und Jarník-Prim-Algorithmus.
Kruskal können die Leistung verbessern, wenn die Kanten sortiert werden können, in der linearen Zeit, oder sind bereits sortiert.
Prim ist besser, wenn die Anzahl der Kanten zu Knoten hoch.
Wenn wir aufhören, den Algorithmus in mittleren prim ' s Algorithmus erzeugt immer angeschlossen Baum, aber kruskal auf der anderen Seite geben kann, getrennt, Baum oder Wald
Kruskal Zeit Komplexität schlimmsten Fall ist O(E log E),weil wir müssen das Sortieren der Kanten.
Prim Zeit Komplexität schlimmsten Fall ist O(E log V) mit Priorität oder noch besser, O(E+V log V) mit Fibonacci-Heap.
Wir sollten Sie nutzen Kruskal wenn der graph Dünn, ich.e.kleine Anzahl von Kanten,E=O(V),wenn die Kanten bereits sortiert sind oder wenn wir diese Sortieren in linearer Zeit.
Wir verwenden sollten, Prim, wenn der graph dicht ist, ich.e die Anzahl der Kanten ist hoch ,wie E=O(V2).
Eine wichtige Anwendung des Kruskal-Algorithmus ist in single-link-clustering.
Betrachten n vertices und Sie haben einen vollständigen Graphen.Erhalten Sie eine k-Cluster dieser n Punkte.Ausführen von Kruskal der Algorithmus über die ersten n-(k-1) Kanten der sortierten Menge von Kanten.Sie erhalten k-cluster des Graphen mit maximalen Abstand.
Die beste Zeit für Kruskal ist O(E, logV). Für Prim ' s mit fib-heaps können wir erhalten O(E+V lgV). Daher auf einem dichten Graphen, Prim ' s ist viel besser.
Prim ist besser für Dichte Graphen, und in diesem wir haben auch nicht zu viel Aufmerksamkeit zu schenken Zyklen durch hinzufügen einer Kante, so sind wir in Erster Linie den Umgang mit Knoten. Prim 's ist schneller als Kruskal' s im Fall der komplexen Graphen.
In kruskal-Algorithmus haben wir die Anzahl der Kanten und die Anzahl der Scheitelpunkte auf einer gegebenen Graphen aber auf jedem edge-wir haben einige Wert oder Gewicht, in deren Auftrag wir bereiten für Sie eine neue Grafik, die muss nicht zyklisch oder nicht in der Nähe von jeder Seite
Zum Beispiel
graph wie dieser
_____________
| | |
| | |
|__________| |
Geben Sie den Namen an jeder Ecke, a,b,c,d,e,f .