ℹ️ Kruskal & Prim — Minimaler Spannbaum
Stell dir vor, du willst 9 Städte mit Stromleitungen verbinden — so günstig wie möglich. Du brauchst genau 8 Leitungen (eine weniger als Städte), damit jede Stadt Strom bekommt, ohne dass irgendwo ein unnötiger Kreis entsteht. Dieses Netz aus minimalen Verbindungen nennt man minimalen Spannbaum (MST).
Genauer gesagt gilt: Ein Spannbaum …
- … verbindet alle Knoten des Graphen
- … enthält keine Kreise
- … hat die kleinstmögliche Gesamtgewichtssumme aller Kanten
Kruskal und Prim sind zwei verschiedene Algorithmen, die denselben MST finden — nur auf unterschiedlichem Weg. Im Modus Beide kannst du sehen, wie sie Schritt für Schritt zum gleichen Ergebnis kommen.
Ein Greedy-Algorithmus zur Berechnung des minimalen Spannbaums (MST) eines gewichteten Graphen. Der MST verbindet alle Knoten mit der kleinstmöglichen Gesamtkantengewichtssumme — ohne Kreise. Kruskal eignet sich besonders für dünne Graphen und arbeitet global auf allen Kanten.
Anwendungen: Netzwerkplanung, Stromversorgung, Cluster-Analyse.
- Sortieren — Alle Kanten aufsteigend nach Gewicht sortieren.
- Auswählen — Die leichteste verbleibende Kante nehmen.
- Kreis prüfen — Kante hinzufügen, falls sie keinen Kreis erzeugt (Union-Find).
- Wiederholen — Bis der Baum n−1 Kanten hat.
Ebenfalls ein Greedy-Algorithmus für den minimalen Spannbaum, der jedoch den Baum schrittweise von einem Startknoten aus wachsen lässt. Statt alle Kanten zu betrachten, wählt Prim immer die günstigste Verbindung zur bereits besuchten Menge. Eignet sich besonders für dichte Graphen.
Anwendungen: Netzwerkplanung, Routing, Maze-Generierung.
- Start — Beliebigen Startknoten in den Baum aufnehmen.
- Kandidaten — Alle Kanten betrachten, die einen Baumknoten mit einem Nicht-Baumknoten verbinden.
- Günstigste wählen — Die Kante mit dem kleinsten Gewicht hinzufügen.
- Wiederholen — Bis alle Knoten im Baum sind.
Alle 13 Kanten nach Gewicht sortiert: B–G (1), C–D (1), A–B (2), A–G (2), B–C (2), …
Wir gehen sie der Reihe nach durch und fügen jede hinzu, die keinen Kreis erzeugt.
Kanten: 0 | Kosten: 0