Algorithmus von Kruskal

Der Algorithmus von Kruskal ist ein Algorithmus der Graphentheorie mit dessen Hilfe man minimale Spannbäume in zusammenhängenden, ungerichteten, kantengewichteten Graphen berechnen kann. Der Algorithmus wurde von Joseph Kruskal geschrieben und erschien erstmals 1956 in der Zeitschrift „Proceedings of the American Mathematical Society“.

Wendet man den Algorithmus auf unzusammenhängende Graphen an, so berechnet er einen minimalen Wald, also minimal spannende Bäume für jede Zusammenhangskomponente des Graphen.

Algorithmus

Die Grundidee ist, die Kanten in Reihenfolge aufsteigender Kantengewichte zu durchlaufen und jede Kante zur Lösung hinzuzufügen, die mit allen zuvor gewählten Kanten keinen Kreis bildet. Es werden somit sukzessiv sogenannte Komponenten zum minimalen Spannbaum verbunden.

Input

Als Eingabe dient ein zusammenhängender kantenbewerteter Graph $G=(V,\,E,\,w)$ . $V$ bezeichnet die Menge der Ecken (vertices), $E$ die Menge der Kanten (edges). Die Gewichtsfunktion $w:E\rightarrow \mathbb {N}$ ordnet jeder Kante ein Kantengewicht zu.

Output

Der Algorithmus liefert einen minimalen Spannbaum $T_{min}(G)=(V,\,E')$ mit $E'\subseteq E$ .

Algorithmus

Der Algorithmus von Kruskal arbeitet nicht deterministisch, d.h. er liefert unter Umständen beim wiederholten Ausführen unterschiedliche Ergebnisse. Alle diese Ergebnisse sind minimale Spannbäume von $G$ .

 $G=(V,E,w)$ : ein zusammenhängender, ungerichteter, kantengewichteter Graph

kruskal(G)
1  Sortiere die Kanten von  $G$  aufsteigend nach ihrem Kantengewicht.
2   $E'\leftarrow \emptyset$ 
3   $L\leftarrow E$ 
4  solange  $\left|E'\right|<\left|V\right|+1$ 
5      wähle eine Kante  $e\in L$  mit kleinstem Kantengewicht
6      entferne die Kante  $e$  aus  $L$ 
7      wenn der Graph  $(V,E'\cup e)$  keinen Kreis enthält
8          dann  $E'\leftarrow E'\cup e$ 
9   $(V,E')$  ist ein minimaler Spannbaum von  $G$ .

Derselbe Algorithmus lässt sich analog für einen maximalen Spannbaum anwenden. Dazu müssen in Zeile 1 die Kanten absteigend sortiert und in Zeile 5 muss eine Kante mit größtem Kantengewicht gewählt werden.

Beispiel

Korrektheitsbeweis

Hinweis: Der Beweis ist zur Zeit falsch, da der Algorithmus umgeschrieben worden ist!

Um die Korrektheit des Algorithmus von Kruskal zu beweisen, muss folgendes gezeigt werden:

der Algorithmus terminiert (er enthält keine Endlosschleife).
der Algorithmus erzeugt einen Spannbaum des vorgegebenen Graphen.
der vom Algorithmus erzeugte Stammbaum ist minimal.

Im Folgenden werden nun dieses Aussagen alle einzeln bewiesen:

Terminiertheit: In jedem Schritt wird ein Knoten des Eingabe-Graphen dem Ausgabe-Graphen hinzugefügt. Da der Eingabe-Graph nur endlich viele Knoten enthält, enthält der Ausgabe-Graph nach endlich vielen Schritten alle Knoten und der Algorithmus determiniert.
Der Algorithmus erzeugt einen Spannbaum des Eingabe-Graphen: Dass $T$ keine Kreise besitzt (d.h. $T$ ein Baum ist), ist nach Schritt 3 klar. Ohne die Einschränkung bei solange in Pkt 3 würde irgendwann jeder Punkt, der überhaupt an einer Kante beteiligt ist, mit $T$ verbunden. Um zu zeigen, dass der Algorithmus nicht zu früh terminiert, beachten wir, dass die Anzahl der Kanten in einem Spannbaum gleich $|V|-k$ mit $k$ als Anzahl der Zusammenhangskomponenten beträgt.
Der erzeugte Spannbaum ist minimal: Der Einfachheit halber nehmen wir an, dass alle Kantengewichte verschieden sind (das kann durch beliebig kleines Verändern der Gewichte erreicht werden). Angenommen, $E'$ ist die an einem gewissen Punkt im Algorithmus gefundene Kantenmenge, und die danach hinzugefügte Kante $e$ liegt nicht in einem minimalen Spannbaum $T$ (wir nehmen also an, der Algorithmus ist nicht korrekt). Der Graph $T\cup e$ hat dann einen Kreis (Spannbaum plus Kante kann kein Baum mehr sein). In diesem Kreis muss es noch eine Kante $e'$ geben, die nicht in $E'$ liegt, sonst würde das Hinzufügen von $e$ einen Kreis erzeugen. Herausschneiden von $e'$ aus $T$ und Ersetzen durch $e$ erzeugt wieder einen Spannbaum, der jedoch von kleinerem Gewicht ist (sonst hätte an dieser Stelle im Algorithmus $e'$ anstelle von $e$ verwendet werden müssen). Es folgt, dass $T$ kein minimaler Spannbaum sein kann, und der Algorithmus ist doch korrekt.

Zeitkomplexität

Im folgenden sei $m$ die Anzahl der Kanten und $n$ die Anzahl der Knoten. Die Laufzeit des Algorithmus beruht im wesentlichen auf dem notwendigen Sortieren der Kanten nach ihren Gewichten und beträgt $O(m\cdot log(m))$ . Insbesondere bei Graphen mit vielen Kanten ist insofern der Algorithmus von Prim effizienter.

Der Algorithmus von Kruskal arbeitet schneller, wenn die Kanten bereits vorsortiert sind. Um dann in konstanter Zeit zu ermitteln, ob eine Kante zwei Komponenten verbindet, wird zu jedem Knoten ein Verweis auf seine Komponente gespeichert. Die Vereinigung von Komponenten ist amortisiert in $O(log(n))$ möglich. Dazu wird zu jeder Komponente ihre Größe gespeichert, so dass bei einer Vereinigung immer die kleinere Komponente der größeren hinzugefügt werden kann. Insgesamt kann somit jeder Knoten höchstens log(n)-mal in eine andere Komponente verschoben werden.

Literatur

J. B. Kruskal: On the shortest spanning subtree and the traveling salesman problem. In: Proceedings of the American Mathematical Society. 7 (1956), S. 48–50

Weblinks

Vollständiger Beweis zur Korrektheit des Algorithmus von Kruskal, Ronny Harbich, 2006