Kruskals Algorithmus - Kruskal's algorithm
Graph und Baumsuchalgorithmen |
---|
Auflistungen |
verwandte Themen |
Kruskals Algorithmus findet einen minimalen Spannwald eines ungerichteten kantengewichteten Graphen . Wenn der Graph verbunden ist , findet er einen minimalen Spannbaum . (Ein minimaler Spannbaum eines verbundenen Diagramms ist eine Teilmenge der Kanten , die einen Baum bildet, der jeden Scheitelpunkt enthält , wobei die Summe der Gewichte aller Kanten im Baum minimiert wird. Für ein nicht verbundenes Diagramm ist ein minimaler Spanning Forest Besteht aus einem minimalen Spannbaum für jede verbundene Komponente .) Dies ist ein gieriger Algorithmus in der Graphentheorie, da in jedem Schritt die Kante mit der nächstniedrigeren Gewichtung hinzugefügt wird, die keinen Zyklus zum minimalen Spanning Forest bildet.
Dieser Algorithmus erschien erstmals 1956 in Proceedings of the American Mathematical Society , S. 48–50, und wurde von Joseph Kruskal geschrieben .
Andere Algorithmen für dieses Problem umfassen den Prim-Algorithmus , den Reverse-Delete-Algorithmus und den Borůvka-Algorithmus .
Algorithmus
- Erstellen Sie einen Wald F (eine Reihe von Bäumen), wobei jeder Scheitelpunkt im Diagramm ein separater Baum ist
- Erstellen Sie eine Menge S, die alle Kanten im Diagramm enthält
- während S ist nicht leer und F ist noch nicht überspannen
- Entfernen Sie eine Kante mit minimalem Gewicht von S.
- Wenn die entfernte Kante zwei verschiedene Bäume verbindet, fügen Sie sie dem Wald F hinzu und kombinieren Sie zwei Bäume zu einem einzigen Baum
Am Ende des Algorithmus bildet die Gesamtstruktur eine minimale Gesamtstruktur des Diagramms. Wenn das Diagramm verbunden ist, besteht die Gesamtstruktur aus einer einzelnen Komponente und bildet einen minimalen Spannbaum.
Pseudocode
Der folgende Code wird mit einer disjunkten Datenstruktur implementiert . Hier stellen wir unsere Gesamtstruktur F als eine Menge von Kanten dar und verwenden die Datenstruktur mit disjunkten Mengen, um effizient zu bestimmen, ob zwei Scheitelpunkte Teil desselben Baums sind.
algorithm Kruskal(G) is F:= ∅ for each v ∈ G.V do MAKE-SET(v) for each (u, v) in G.E ordered by weight(u, v), increasing do if FIND-SET(u) ≠ FIND-SET(v) then F:= F ∪ {(u, v)} ∪ {(v, u)} UNION(FIND-SET(u), FIND-SET(v)) return F
Komplexität
Für ein Diagramm mit E- Kanten und V- Eckpunkten kann gezeigt werden, dass der Kruskal-Algorithmus in O ( E log E ) -Zeit oder äquivalent in O ( E log V ) -Zeit ausgeführt wird, alle mit einfachen Datenstrukturen. Diese Laufzeiten sind äquivalent, weil:
- E ist höchstens und .
- Jeder isolierte Scheitelpunkt ist eine separate Komponente des minimalen überspannenden Waldes. Wenn wir Eckpunkte isoliert ignore erhalten wir V ≤ 2 E , so log V ist .
Wir können diese Grenze wie folgt erreichen: Sortieren Sie zuerst die Kanten nach Gewicht unter Verwendung einer Vergleichssortierung in O ( E log E ) -Zeit; Dadurch kann der Schritt "Entfernen einer Kante mit minimalem Gewicht von S " in konstanter Zeit ausgeführt werden. Als Nächstes verwenden wir eine disjunkte Datenstruktur , um zu verfolgen, welche Scheitelpunkte sich in welchen Komponenten befinden. Wir platzieren jeden Scheitelpunkt in einer eigenen disjunkten Menge, die O ( V ) -Operationen ausführt. Schließlich müssen wir im schlimmsten Fall alle Kanten durchlaufen, und für jede Kante müssen wir zwei Suchoperationen und möglicherweise eine Vereinigung ausführen. Sogar eine einfache Datenstruktur mit disjunkten Mengen, wie z. B. Gesamtstrukturen mit disjunkten Mengen und Vereinigung nach Rang, kann O ( E ) -Operationen in O ( E log V ) -Zeit ausführen . Somit ist die Gesamtzeit O ( E log E ) = O ( E log V ).
Vorausgesetzt, die Kanten sind entweder bereits sortiert oder können in linearer Zeit sortiert werden (z. B. mit Zählsortierung oder Radix-Sortierung ), kann der Algorithmus eine komplexere Datenstruktur mit disjunkten Mengen verwenden , um in O ( E α ( V )) -Zeit zu laufen wobei α das extrem langsam wachsende Inverse der einwertigen Ackermann-Funktion ist .
Beispiel
Bild | Beschreibung |
---|---|
AD und CE sind die kürzesten Kanten mit der Länge 5, und AD wurde willkürlich ausgewählt, sodass es hervorgehoben wird. | |
CE ist jetzt die kürzeste Kante, die keinen Zyklus bildet, mit der Länge 5, sodass sie als zweite Kante hervorgehoben wird. | |
Die nächste Kante, DF mit der Länge 6, wird mit der gleichen Methode hervorgehoben. | |
Die nächstkürzesten Kanten sind AB und BE , beide mit der Länge 7. AB wird willkürlich gewählt und hervorgehoben. Die Kante BD wurde rot hervorgehoben, da bereits ein Pfad (grün) zwischen B und D vorhanden ist , sodass sie bei Auswahl einen Zyklus ( ABD ) bilden würde. | |
Der Prozess hebt weiterhin die nächstkleinere Kante BE mit der Länge 7 hervor. In diesem Stadium werden viele weitere Kanten rot hervorgehoben: BC, weil sie die Schleife BCE bilden würde , DE, weil sie die Schleife DEBA bilden würde , und FE, weil dies der Fall wäre bilden FEBAD . | |
Schließlich endet der Prozess mit der Kante EG der Länge 9, und der minimale Spannbaum wird gefunden. |
Nachweis der Richtigkeit
Der Beweis besteht aus zwei Teilen. Zunächst wird bewiesen, dass der Algorithmus einen Spanning Tree erzeugt . Zweitens ist bewiesen, dass der konstruierte Spannbaum ein minimales Gewicht hat.
Spanning Tree
Sei ein zusammenhängender, gewichteter Graph und sei der vom Algorithmus erzeugte Teilgraph . kann keinen Zyklus haben, da per Definition keine Kante hinzugefügt wird, wenn dies zu einem Zyklus führt. kann nicht getrennt werden, da die erste angetroffene Kante, die zwei Komponenten von verbindet, vom Algorithmus hinzugefügt worden wäre. Somit ist ein Spannbaum von .
Minimalität
Wir zeigen, dass der folgende Satz P durch Induktion wahr ist : Wenn F die Menge von Kanten ist, die in einer beliebigen Phase des Algorithmus ausgewählt wurde, gibt es einen minimalen Spannbaum, der F enthält, und keine der vom Algorithmus zurückgewiesenen Kanten.
- Es ist klar, dass P am Anfang wahr ist, wenn F leer ist: Jeder minimale Spannbaum reicht aus, und es gibt einen, weil ein gewichteter verbundener Graph immer einen minimalen Spannbaum hat.
- Nehmen wir nun an, dass P für eine nicht endgültige Kantenmenge F gilt, und lassen Sie T einen minimalen Spannbaum sein, der F enthält .
- Wenn die nächste gewählte Kante e auch ist T , dann P ist für echtes F + e .
- Andernfalls, wenn e nicht in ist T dann T + E hat einen Zyklus C . Dieser Zyklus enthält Kanten , die zu nicht gehören F , da e nicht einen Zyklus bilden , wenn hinzugefügt F aber tut in T . Sei f eine Kante, die in C, aber nicht in F + e ist . Beachten Sie, dass f auch zu T gehört und von P vom Algorithmus nicht berücksichtigt wurde. f muss daher ein Gewicht haben, das mindestens so groß ist wie e . Dann T - f + e ist ein Baum, und es hat das gleiche oder weniger Gewicht als T . So T - f + e ist ein Minimum Spanning Tree enthält F + E und wieder P hält.
- Nach dem Induktionsprinzip gilt P daher, wenn F zu einem Spannbaum geworden ist, was nur möglich ist, wenn F selbst ein minimaler Spannbaum ist.
Paralleler Algorithmus
Kruskals Algorithmus ist von Natur aus sequentiell und schwer zu parallelisieren. Es ist jedoch möglich, die anfängliche Sortierung der Kanten parallel durchzuführen oder alternativ eine parallele Implementierung eines binären Heaps zu verwenden, um die Kante mit dem minimalen Gewicht in jeder Iteration zu extrahieren. Da auf Prozessoren zeitlich eine parallele Sortierung möglich ist , kann die Laufzeit des Kruskal-Algorithmus auf O ( E α ( V )) reduziert werden , wobei α wiederum die Umkehrung der einwertigen Ackermann-Funktion ist .
Eine Variante des Kruskal-Algorithmus namens Filter-Kruskal wurde von Osipov et al. und ist besser für die Parallelisierung geeignet. Die Grundidee von Filter-Kruskal besteht darin, die Kanten ähnlich wie beim Quicksortieren zu partitionieren und Kanten herauszufiltern, die Scheitelpunkte desselben Baums verbinden, um die Kosten für das Sortieren zu senken. Der folgende Pseudocode demonstriert dies.
function filter_kruskal(G) is if |G.E| < kruskal_threshold: return kruskal(G) pivot = choose_random(G.E) , = partition(G.E, pivot) A = filter_kruskal() = filter() A = A ∪ filter_kruskal() return A function partition(E, pivot) is = ∅, = ∅ foreach (u, v) in E do if weight(u, v) <= pivot then = ∪ {(u, v)} else = ∪ {(u, v)} return , function filter(E) is = ∅ foreach (u, v) in E do if find_set(u) ≠ find_set(v) then = ∪ {(u, v)} return
Filter-Kruskal eignet sich besser für die Parallelisierung, da das Sortieren, Filtern und Partitionieren einfach parallel durchgeführt werden kann, indem die Kanten zwischen den Prozessoren verteilt werden.
Schließlich wurden andere Varianten einer parallelen Implementierung des Kruskal-Algorithmus untersucht. Beispiele sind ein Schema, das Hilfsthreads verwendet, um Kanten zu entfernen, die definitiv nicht Teil des MST im Hintergrund sind, und eine Variante, die den sequentiellen Algorithmus auf p Untergraphen ausführt und diese Untergraphen dann zusammenführt, bis nur noch einer, der endgültige MST, übrig bleibt.
Siehe auch
- Prims Algorithmus
- Dijkstras Algorithmus
- Borůvkas Algorithmus
- Reverse-Delete-Algorithmus
- Single-Linkage-Clustering
- Gieriger geometrischer Schraubenschlüssel
Verweise
- Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest und Clifford Stein . Einführung in Algorithmen , 2. Auflage. MIT Press und McGraw-Hill, 2001. ISBN 0-262-03293-7 . Abschnitt 23.2: Die Algorithmen von Kruskal und Prim, S. 567–574.
- Michael T. Goodrich und Roberto Tamassia . Datenstrukturen und Algorithmen in Java , 4. Auflage. John Wiley & Sons, Inc., 2006. ISBN 0-471-73884-0 . Abschnitt 13.7.1: Kruskals Algorithmus, S. 632 ..