Minimaler Spannbaum nach Kruskal (Algorithmus 4.8)

So geht’s: Beim Öffnen läuft der Testclient mit tinyEWG, demselben Graphen wie bei Prim. Erst kommen alle Kanten in die Vorrangwarteschlange. Dann holt delMin() Runde für Runde die leichteste Kante, sie ist blau gestrichelt. Liegen beide Enden schon im selben Baum, leuchtet der Weg rot auf, den es zwischen ihnen schon gibt, und die Kante wird verworfen (danach rot gepunktet). Sonst verschmilzt union die beiden Bäume, und die Kante wird schwarz. Die Knoten eines Baums haben dieselbe Farbe, so sieht man den Wald zusammenwachsen. Rechts steht die Tabelle aus dem Erklärtext, sie füllt sich Kante für Kante. Unter dem Graphen stehen id[] und sz[] des Union-Find. „Zufallsgraph“ erzeugt einen neuen Graphen, manchmal aus zwei Teilen, dann entsteht ein Spannwald. „↺ Neu starten“ springt zurück zu tinyEWG.

Erklärung

Minimaler Spannbaum nach Kruskal (Algorithmus 4.8), Klasse KruskalMST. Gleiche Aufgabe wie Prim [37], anderer Weg.

Idee: Alle Kanten nach Gewicht sortiert durchgehen, von der leichtesten an. Jede Kante nehmen, die keinen Zyklus mit den schon gewählten bildet. Aufhören, sobald V − 1 Kanten beisammen sind.

• Prim lässt einen Baum von einem Startknoten aus wachsen.
• Kruskal baut einen Wald aus vielen kleinen Bäumen, die nach und nach zusammenwachsen, bis einer übrig ist.

Der Code ist ein Zusammenspiel von drei Strukturen aus früheren Kapiteln:

• MinPQ<Edge>: Vorrangwarteschlange [12], hier als Min-Heap, enthält alle Kanten. delMin liefert immer die leichteste noch nicht geprüfte.
• UF: Union-Find [19], [21]. Prüft, ob die beiden Endpunkte schon im selben Baum liegen.
• Queue<Edge> mst: Warteschlange [16], sammelt die gewählten Kanten.
• Schleife: leichteste Kante v–w holen. uf.connected(v, w) → beide schon verbunden, die Kante würde einen Zyklus schließen, verwerfen. Sonst uf.union(v, w) (zwei Bäume verschmelzen) und Kante ins Ergebnis.

Ablauf für tinyEWG.txt (8 Knoten, 16 Kanten), Kanten nach Gewicht:

Gesamtgewicht 1,81. Die schwereren Kanten (3-6, 6-0, 6-4) werden gar nicht mehr angeschaut. Die MST-Kanten kommen automatisch aufsteigend nach Gewicht heraus.

Warum korrekt? Wieder die Schnitteigenschaft aus [37]: Verbindet die Kante v–w zwei verschiedene Bäume, betrachte den Schnitt zwischen dem Baum von v und dem Rest. Alle leichteren Kanten sind schon verarbeitet, also ist v–w die leichteste kreuzende Kante und gehört zum MST.

Satz O: Kruskal braucht Speicher proportional zu E und Zeit proportional zu E log E im schlimmsten Fall. Die Kosten stecken im Heap (E-mal einfügen und entnehmen), die Union-Find-Operationen fallen dagegen kaum ins Gewicht.

Prim vs. Kruskal:

E log E und E log V sind übrigens praktisch dasselbe, weil E höchstens V² ist und damit log E höchstens 2 log V. In der Praxis ist Kruskal meist etwas langsamer als Prim, weil zusätzlich Union-Find-Operationen anfallen, dafür ist er sehr einfach zu verstehen.

Stand Kapitel 4:

• Algorithmus 4.1: Tiefensuche für Pfade [30]
• Algorithmus 4.2: Breitensuche für kürzeste Pfade [31]
• Algorithmus 4.3: Zusammenhangskomponenten [32]
• Algorithmus 4.4: Erreichbarkeit in Digraphen [33]
• Algorithmus 4.5: Topologisches Sortieren [34]
• Algorithmus 4.6: Starke Komponenten nach Kosaraju [35], [36]
• Algorithmus 4.7: Minimaler Spannbaum nach Prim [37]
• Algorithmus 4.8: Minimaler Spannbaum nach Kruskal [38]