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) $O(m\log {n})$. In nicht zusammenhängenden Graphen findet der Algorithmus einen Wald von spannenden Bäumen für jede der Zusammenhangskomponenten.

Die Implementation mit bestmöglicher Laufzeit ist nicht ganz trivial, da man in konstanter Zeit erkennen können muss, ob eine Kante einen Kreis schließt oder zwei Komponenten verbindet. Der Trick ist, sich zu jedem Knoten die Komponente zu merken und wieviele Konten diese enthält. Allerdings hat man nun das Problem, dies beim Einfügen einer Kante ebenfalls in konstanter Zeit zu updaten. Dies ist nur amortiesiert möglich (siehe amortisierte Laufzeitanalyse). Zu jedem Knoten existiert ein Pointer auf ein Integer, welches die Größe der Komponente angibt. Konten der selben Komponente zeigen auf die selbe Integer-Variable (und die verschiedener Komponente auf verschiedene Variablen). Werden zwei Komponenten durch eine neue Kante verbunden, so wird der Wert der Integervariablen entsprechend erhöht und die Pointer der ehemals kleineren Komponente auf das Integer der ehemals größeren Komponente "umgebogen". Es läßt sich zeigen, daß in der Summe höchstens 2n mal (? stimmt das Jakob?) Pointer umgebogen werden müssen, so daß im Schnitt höchstens 2 Pointer umgebogen werden müssen, dieses umbiegen amortiesiert also nur konstant viel Zeit benötigt, obwohl bei einer Verschmelzung von zwei Komponenten bis zu n/2 Pointer pro Schritt umgebogen werden müssen.

Mit Hilfe eines Fibonacci-Heaps und des Algorithmus von Prim läßt sichein Minimal spannender Baum noch etwas effizienter in Laufzeit $O(m+n\log {n})$ bestimmen.

Der Algorithmus

• Sortiere die Menge E aller Kanten nach ihrem Gewicht
• So lange E nicht leer ist
  • Entferne eine Kante mit minimalem Gewicht aus E
  • Wenn diese Kante zwei verschiedene Komponenten (Bäume) verbindet
    • dann kombiniere beide Komponenten (Bäume) und die Kante zu einer neuen Komponente (einen neuen Baum)

Man beachte, das 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.