Algorithmus von Kruskal
Der Algorithmus von Kruskal (nach seinem Erfinder Joseph Kruskal, 1956) dient der Berechnung von minimalen Spannbäumen in zusammenhängenden, ungerichteten, kantengewichteten Graphen. In unzusammenhängenden Graphen berechnet der Algorithmus einen minimalen Wald, also minimal spannende Bäume für jede Zusammenhangskomponente des Graphen.
| Inhaltsverzeichnis |
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 
. V bezeichnet die Menge der Ecken (vertices), E die Menge der Kanten (edges). Die Gewichtsfunktion 
ordnet jeder Kante einen Zahlenwert zu.
Output
Der Algorithmus liefert einen minimalen Spannbaum 
mit 
.
Algorithmus
Der Algorithmus von Kruskal arbeitet nicht deterministisch, d.h. er liefert unter Umständen beim wiederholten Ausführen unterschiedliche Ergebnisse. Diese Ergebnisse sind allesamt minimale Spannbäume von G und damit gleichwertige Lösungen.
- Sortiere die Kanten von G aufsteigend nach ihrer Bewertung.
- Setze
und 
.
- Solange
ist, wähle in L eine Kante e mit kleinster Bewertung. Entferne e aus L.
- Wenn
keinen Kreis enthält, füge e zu E' hinzu.
- Wenn
- Dann ist ein minimaler Spannbaum von G.
Derselbe Algorithmus lässt sich analog für einen maximalen Spannbaum anwenden.
Beispiel
left|framed
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 * log(m)). Insbesondere bei Graphen mit vielen Kanten ist in sofern 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 anderen Komponente verschoben werden.
Siehe auch
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
Kruskal, Algorithmus von Kategorie:Graphentheorie Kategorie:Mathematical Subject Classification 05C85 Kategorie:Optimierungsalgorithmus