Overview
Kruskals Algorithmus findet den minimalen Spannbaum durch gieriges Hinzufügen der günstigsten Kante ohne Zyklus.
Analogy
Stromleitungen zwischen Städten legen: immer das billigste Kabelpaar verbinden, das noch nicht indirekt verbunden ist.
Step-by-step
- Alle Kanten nach Gewicht aufsteigend sortieren.
- Für jede Kante (u,v,w): wenn find(u) != find(v): Kante hinzufügen und union(u,v).
- Stoppen wenn V-1 Kanten hinzugefügt (Spannbaum vollständig).
- Union-Find mit Pfadkompression und Rang verwenden.
Visual
Kanten sortiert: (1,2,1),(1,3,2),(2,4,2),(3,4,3) → MST verwendet erste 3 Kanten, Gesamtgewicht 5.
Common mistakes
- Kanten nicht zuerst sortieren.
- Union-Find weglassen → Zyklusprüfung ist O(V) pro Kante statt O(α(V)).
Practice questions
- Kruskal mit Union-Find implementieren; MST-Gewicht ausgeben.
- Kruskal vs. Prim für dichte vs. sparse Graphen vergleichen.