Wann sollte ich Kruskal im Gegensatz zu Prim verwenden (und umgekehrt)?

Ich habe mich gefragt, wann man Prims Algorithmus verwenden sollte und wann Kruskals , um den minimalen Spannbaum zu finden. Beide haben eine einfache Logik, dieselben schlimmsten Fälle, und der einzige Unterschied besteht in der Implementierung, die möglicherweise etwas unterschiedliche Datenstrukturen umfasst. Was ist der entscheidende Faktor?

Verwenden Sie den Prim-Algorithmus, wenn Sie ein Diagramm mit vielen Kanten haben.

Bei einem Graphen mit V Eckpunkten E Kanten wird der Kruskal-Algorithmus in der Zeit O (E log V) und der Prim-Algorithmus in der amortisierten Zeit O (E + V log V) ausgeführt , wenn Sie einen Fibonacci-Heap verwenden .

Der Algorithmus von Prim ist im Limit deutlich schneller, wenn Sie ein wirklich dichtes Diagramm mit viel mehr Kanten als Scheitelpunkten haben. Kruskal bietet in typischen Situationen eine bessere Leistung (spärliche Diagramme), da es einfachere Datenstrukturen verwendet.

Ich habe im Internet einen sehr schönen Thread gefunden, der den Unterschied auf sehr einfache Weise erklärt: http://www.thestudentroom.co.uk/showthread.php?t=232168 .

Der Kruskal-Algorithmus wird eine Lösung von der billigsten Kante aus hinzufügen, indem die nächstbilligste Kante hinzugefügt wird, vorausgesetzt, er erzeugt keinen Zyklus.

Der Prim-Algorithmus vergrößert eine Lösung aus einem zufälligen Scheitelpunkt, indem er den nächstbilligsten Scheitelpunkt hinzufügt, den Scheitelpunkt, der sich derzeit nicht in der Lösung befindet, aber durch die billigste Kante mit ihm verbunden ist.

Hier ist ein interessantes Blatt zu diesem Thema beigefügt.

Wenn Sie sowohl Kruskal als auch Prim in ihrer optimalen Form implementieren: mit einem Union Find bzw. einem Finbonacci-Heap, werden Sie feststellen, wie einfach Kruskal im Vergleich zu Prim zu implementieren ist.

Prim ist mit einem Fibonacci-Heap schwieriger, hauptsächlich weil Sie eine Buchhaltungstabelle führen müssen, um die bidirektionale Verbindung zwischen Graphknoten und Heapknoten aufzuzeichnen. Bei einem Union Find ist das Gegenteil der Fall, die Struktur ist einfach und kann sogar fast ohne zusätzliche Kosten direkt das erste produzieren.

Ich weiß, dass Sie nicht danach gefragt haben, aber wenn Sie mehr Verarbeitungseinheiten haben, sollten Sie immer den Borůvka-Algorithmus in Betracht ziehen , da er leicht parallelisiert werden kann - daher hat er einen Leistungsvorteil gegenüber dem Kruskal- und dem Jarník-Prim-Algorithmus.

Kruskal kann eine bessere Leistung erzielen, wenn die Kanten in linearer Zeit sortiert werden können oder bereits sortiert sind.

Prim ist besser, wenn die Anzahl der Kanten zu Eckpunkten hoch ist.

Der schlimmste Fall der Kruskal- Zeitkomplexität ist O (E log E) , weil wir die Kanten sortieren müssen. Der schlimmste Fall der Komplexität der Prim- Zeit ist O (E log V) mit Prioritätswarteschlange oder noch besser O (E + V log V) mit Fibonacci-Heap . Wir sollten Kruskal verwenden, wenn der Graph dünn ist, eine kleine Anzahl von Kanten, wie E = O (V), wenn die Kanten bereits sortiert sind oder wenn wir sie in linearer Zeit sortieren können. Wir sollten Prim verwenden, wenn der Graph dicht ist, dh die Anzahl der Kanten hoch ist, wie E = O (V²).

Wenn wir den Algorithmus im mittleren Prim stoppen, generiert der Algorithmus immer einen verbundenen Baum, aber kruskal kann andererseits einen getrennten Baum oder Wald ergeben

Eine wichtige Anwendung des Kruskal-Algorithmus ist das Single-Link-Clustering .

Betrachten Sie n Eckpunkte und Sie haben ein vollständiges Diagramm. Um ak-Cluster dieser n Punkte zu erhalten. Führen Sie den Kruskal-Algorithmus über die ersten n- (k-1) Kanten des sortierten Satzes von Kanten aus. Sie erhalten k-Cluster des Diagramms mit Maximum Abstand.

Die beste Zeit für Kruskal ist O (E logV). Für Prim, die Fib-Haufen verwenden, können wir O (E + V lgV) erhalten. Daher ist Prims in einem dichten Diagramm viel besser.

Prims sind besser für dichtere Graphen, und dabei müssen wir auch den Zyklen durch Hinzufügen einer Kante nicht viel Aufmerksamkeit schenken, da wir uns hauptsächlich mit Knoten befassen. Prims ist bei komplexen Graphen schneller als Kruskals.

Im Kruskal-Algorithmus haben wir die Anzahl der Kanten und die Anzahl der Eckpunkte in einem bestimmten Diagramm, aber an jeder Kante haben wir einen Wert oder ein Gewicht, für das wir ein neues Diagramm erstellen können, das nicht zyklisch sein oder von keiner Seite schließen darf. Zum Beispiel

Grafik wie diese _____________ | | | | | | | __________ | | Geben Sie jedem Scheitelpunkt a, b, c, d, e, f einen Namen.