Algorithmus von Kruskal

Zweck und Grundprinzip

Der Algorithmus von Kruskal ist ein Greedy-Algorithmus der Graphentheorie zur Berechnung eines minimalen Spannbaums. Ein Spannbaum verbindet alle Knoten eines ungerichteten Graphen ohne Kreise; ein minimaler Spannbaum besitzt unter allen solchen Bäumen die kleinste Summe der Kantengewichte. Voraussetzung ist ein endlicher, zusammenhängender und kantengewichteter Graph. Als Kantengewicht gilt dabei ein Wert, der einer Kante zugeordnet ist.

Kruskal wurde 1956 von Joseph Kruskal in den „Proceedings of the American Mathematical Society“ veröffentlicht. Die Regel lautet: Wiederholt wird die kürzeste noch nicht ausgewählte Kante gewählt, sofern sie zusammen mit den bereits gewählten Kanten keinen Kreis bildet. „Kürzeste“ bedeutet: Kante mit dem kleinsten Gewicht.

Das Verfahren sortiert zunächst alle Kanten aufsteigend nach ihrem Gewicht. Anschließend werden sie in dieser Reihenfolge betrachtet. Eine Kante wird genau dann übernommen, wenn ihre beiden Endknoten noch nicht durch einen Pfad aus bereits gewählten Kanten verbunden sind. Dadurch verbindet jede übernommene Kante zwei bisher getrennte Komponenten, also Teilgraphen, zu einer größeren Komponente. Bei gleichen Kantengewichten können verschiedene zulässige Kanten gewählt werden. Der Algorithmus ist deshalb nicht-deterministisch: Mehrere Durchläufe können unterschiedliche, aber jeweils minimale Spannbäume liefern.

Bei einem unzusammenhängenden Graphen entsteht nicht ein einzelner Spannbaum. Stattdessen berechnet Kruskal für jede Zusammenhangskomponente einen minimalen Spannbaum; zusammen bilden diese Bäume einen minimalen aufspannenden Wald.

Eingabe, Ausgabe und Ablauf

Die Eingabe ist ein zusammenhängender, ungerichteter, kantengewichteter Graph G = (V, E, w). V ist die Menge der Knoten, E die Menge der Kanten und die Gewichtsfunktion w: E → ℝ ordnet jeder Kante ein Kantengewicht zu. Die Ausgabe ist ein minimaler Spannbaum M = (V, E′) mit E′ ⊆ E.

Der Pseudocode setzt zunächst E′ ← ∅ und L ← E. Danach werden die Kanten in L aufsteigend nach ihrem Gewicht sortiert. Solange L nicht leer ist, wird eine Kante e mit kleinstem Gewicht ausgewählt und aus L entfernt. Enthält der Graph (V, E′ ∪ {e}) keinen Kreis, wird e zu E′ hinzugefügt. Am Ende ist M = (V, E′) der minimale Spannbaum.

Für einen maximalen Spannbaum kann derselbe Ansatz verwendet werden. Dazu wird G = (V, E, w) in G′ = (V, E, w′) mit w′(e) = s − w(e) umgewandelt, wobei s ∈ ℕ und für alle e ∈ E gilt: s > w(e). Ein minimaler Spannbaum von G′ entspricht dann einem maximalen Spannbaum von G.

Beispiel

Im dargestellten Beispiel sind AD und CE die kürzesten Kanten. Zuerst wird zufällig AD gewählt, danach CE; beide bilden keinen Kreis. Anschließend wird DF mit Länge 6 übernommen.

Von den Kanten AB und BE mit jeweils Länge 7 wird zunächst AB gewählt. BD würde mit den bereits gewählten Kanten einen Kreis bilden und wird daher verworfen. Danach wird BE gewählt. Dadurch würden auch BC, DE und FE Kreise erzeugen und können nicht mehr berücksichtigt werden. Als letzte Kante wird EG mit Länge 9 ausgewählt. FG wird verworfen, weil auch diese Kante einen Kreis bilden würde. Der so entstandene grüne Graph ist ein minimaler Spannbaum.

Korrektheit

Der Algorithmus terminiert, weil in jedem Schleifendurchlauf genau eine Kante aus L entfernt wird. Da L zu Beginn E ist und E endlich ist, kann die Schleife nur endlich oft ausgeführt werden.

Die Ausgabe M ist ein aufspannender Teilgraph von G: Beide Graphen besitzen dieselbe Knotenmenge V, und es gilt E′ ⊆ E. M enthält keinen Kreis, weil eine Kante nur dann aufgenommen wird, wenn sie keinen Kreis erzeugt. M ist außerdem zusammenhängend. Wäre dies nicht der Fall, gäbe es zwei in M nicht durch einen Weg verbundene Knoten x und y. Da G zusammenhängend ist, gibt es eine Kante k aus G, die solche getrennten Teile verbindet. Beim Betrachten von k würde kein Kreis entstehen; der Algorithmus müsste k also einfügen. Das widerspricht der Annahme, dass M nicht zusammenhängend ist.

Die Minimalität wird durch Induktion begründet. Nach jedem Schritt gibt es einen minimalen Spannbaum, der alle bisher von Kruskal gewählten Kanten enthält. Wird eine neue Kante e gewählt, die nicht in einem solchen minimalen Spannbaum H liegt, erzeugt H + e einen Kreis. Aus diesem Kreis kann eine nicht schon gewählte Kante f entfernt werden. Weil Kruskal e vor f gewählt hat, gilt w(e) ≤ w(f). Daher ist H − f + e nicht schwerer als H und wegen der Minimalität von H ebenfalls ein minimaler Spannbaum. Am Ende ist die erzeugte kreisfreie und zusammenhängende Kantenmenge somit minimal.

Laufzeit, Datenstruktur und Parallelisierung

Die Laufzeit besteht vor allem aus dem Sortieren und der Kreisprüfung. Das Sortieren benötigt O(|E| · log(|E|)). Bei einer geeigneten Umsetzung bestimmt es die Gesamtlaufzeit; insbesondere bei Graphen mit vielen Kanten ist der Algorithmus von Prim effizienter.

Zur Kreisprüfung eignet sich eine Union-Find-Struktur. Sie speichert, welche Knoten bereits zusammenhängen, als Partitionen. Find(x) liefert einen Repräsentanten der Partition von x. Für eine Kante (v₁, v₂) wird geprüft, ob Find(v₁) und Find(v₂) verschieden sind. Nur dann wird die Kante aufgenommen und die beiden Partitionen werden mit Union vereinigt. Find wird insgesamt 2 · |E| Mal, Union |V| − 1 Mal aufgerufen. Mit Union-By-Size und Pfadkompression beträgt die amortisierte Laufzeit für diesen Teil O(|E| · α(|V|)); α ist die inverse Ackermannfunktion und für realistische Eingaben stets kleiner oder gleich 5. Allgemein ergibt sich mit Union-Find O(T_sort(|E|) + |E| · α(|V|)).

Das anfängliche Sortieren kann parallel ausgeführt werden, die anschließende Auswahl der Kanten muss für die Korrektheit jedoch nacheinander erfolgen. Mit O(log |V|) Prozessoren kann das Sortieren laut Darstellung in linearer Zeit erfolgen; dadurch sinkt die Gesamtlaufzeit auf O(|E| · α(|V|)). Eine weitere Angabe nennt paralleles Sortieren auf O(n · log n) Prozessoren in O(n) Zeit und eine Laufzeit von O(|E| · log*|V|).

Filter-Kruskal ist eine besser parallelisierbare Variante von Osipov et al. Sie wählt eine zufällige Pivot-Kante, teilt die Kanten ähnlich wie Quicksort in E≤ und E> auf und bearbeitet zuerst E≤ rekursiv. Danach filtert sie aus E> alle Kanten, deren Endknoten bereits im selben Teilbaum liegen. Erst dann wird der verbleibende Teil E> rekursiv bearbeitet. Sortieren, Partitionieren und Filtern lassen sich dabei durch Aufteilen der Kanten auf Prozessoren parallel ausführen.