Motivation

Kruskal verwaltet den wachsenden Wald aus ausgewählten Kanten in einer union-find-Struktur. Um eine Kante sicher hinzuzufügen, wird geprüft, ob sich die beiden Endpunkte bereits in derselben Menge befinden (das würde einen Zyklus erzeugen).

Warum Kruskal lernen?

• Echte MSTs: Netzwerkdesign, Clustering und das Verlegen von Kabeln oder Straßen zu minimalen Kosten.
• Union-find: eine schöne, wiederverwendbare Struktur zur Verfolgung der Konnektivität, die überall in der Informatik vorkommt.
• Greedy-Korrektheit: ein weiteres Beispiel dafür, dass das ständige Wählen der günstigsten sicheren Option zum globalen Optimum führt.

Alle minimalen Spannbäume eines Graphen verwenden dieselbe Multimenge von Kantengewichten, sodass das Gesamtgewicht (und die größte Kante) eindeutig ist.