Algorithmus von Kruskal
Der Algorithmus von Kruskal ist ein Algorithmus zur Berechnung von
minimal spannenden Bäumen in zusammenhängenden ungerichteten Graphen.
Die Grundidee ist dabei, immer die jeweils leichteste Kante hinzuzufügen, bei der dadurch kein Kreis entsteht. Die Laufzeit des Algorithmus beruht im wesentlichen auf dem notwendigen sortieren der Kanten und beträgt (zum Beispiel unter der Verwendung von Heapsort) . In nicht zusammenhängenden Graphen findet der Algorithmus einen Wald von spannenden Bäumen für jede der Zusammenhangskomponenten.
Mit Hilfe eines Fibonacci-Heaps und des Algorithmus von Prim läßt sich ein minimal spannender Baum noch etwas effizienter in Laufzeit bestimmen.
Implementation des Kruskal-Algorithmus
- Sei E die Menge aller Kanten
- So lange Kanten in E übrig sind
- Entferne eine Kante mit minimalem Gewicht
- Wenn diese Kante zwei verschiedene Komponenten verbindet
- Vereinige beide Komponenten und die Kante zu einer neuen Komponente
Man beachte, dass die Komponenten immer Bäume sind (also selbst kreisfrei), und das Verbinden zweier Komponenten durch eine Kante eine neue Komponente ergibt, die selbst Baum (also kreisfrei) ist.
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 nur amorisiert in konstanter Zeit 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. Man kann zeigen, dass jede Kante insgesamt nur an einer Vereinigung beteiligt ist, so dass jede Vereinigung durchschnittlich konstante Zeit benötigt.