Algorithmus von Kruskal

Der Algorithmus von Kruskal (1956) ist ein Algorithmus zur Berechnung von minimal spannenden Bäumen in zusammenhängenden ungerichteten kantengewichteten Graphen. In unzusammenhängenden Graphen berechnet der Algorithmus ein minimales Gerüst, also minimal spannende Bäume für jede Zusammenhangskomponente des Graphen.

Grundidee

Die Grundidee ist, die Kanten in Reihenfolge aufsteigender Kantengewichte zu durchlaufen und jede Kante zu wählen, die mit allen zuvor gewählten Kanten keinen Kreis schließt. Die Laufzeit des Algorithmus beruht im wesentlichen auf dem notwendigen Sortieren der Kanten und beträgt $O(n+m\log n),$ wobei m die Zahl der Kanten und n die Zahl der Knoten ist.

Implementation des Kruskal-Algorithmus

Zur Bestimmung der leichtesten Kante wird die Menge E in der Regel sortiert. Zur Implementation mit bestmöglicher Laufzeit muss in konstanter Zeit ermittelt werden, ob eine Kante zwei Komponenten verbindet und damit zum minimalen Spannbaum gehört oder ob sie einen Kreis schließen würde und daher verworfen werden soll.

Dazu 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 anderen Komponente verschoben werden.

Algorithmus von Prim

Mit Hilfe von Fibonacci-Heaps und des Algorithmus von Prim lässt sich ein minimal spannender Baum noch etwas effizienter in Laufzeit $O(m+n\log n)$ bestimmen.