Algorithmus von Kruskal
Der Algorithmus von Kruskal (1956) ist ein Algorithmus zur Berechnung von minimal spannenden Bäumen in zusammenhängenden ungerichteten kantengewichteten Graphenen.
Table of contents |
2 Implementation des Kruskal-Algorithmus 3 Algorithmus von Prim |
Grundidee
Die Grundidee ist, die Kanten in der 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 wobei m die Zahl der Kanten und n die Zahl der Knoten ist.
In unzusammenhängenden Graphen findet der Algorithmus einen Wald von spannenden Bäumen für jede der Zusammenhangskomponenten.
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.
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.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 bestimmen.