Kruskals Algorithmus - Kruskal's algorithm

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

Eine Demo für Kruskals Algorithmus in einem vollständigen Diagramm mit Gewichten basierend auf der euklidischen Entfernung.

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
Kruskal-Algorithmus 1.svg AD und CE sind die kürzesten Kanten mit der Länge 5, und AD wurde willkürlich ausgewählt, sodass es hervorgehoben wird.
Kruskal-Algorithmus 2.svg CE ist jetzt die kürzeste Kante, die keinen Zyklus bildet, mit der Länge 5, sodass sie als zweite Kante hervorgehoben wird.
Kruskal-Algorithmus 3.svg Die nächste Kante, DF mit der Länge 6, wird mit der gleichen Methode hervorgehoben.
Kruskal-Algorithmus 4.svg 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.
Kruskal-Algorithmus 5.svg 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 .
Kruskal-Algorithmus 6.svg 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

Verweise

Externe Links