Minimaler Spannbaum: Netzwerke mit minimalen Kosten verbinden (Kruskal und Prim)

Minimaler Spannbaum (Minimum Spanning Tree, MST) heißt ein Teilgraph eines zusammenhängenden, gewichteten Graphen, der alle Knoten verbindet, ein Baum ist (also keine Zyklen enthält) und die Summe seiner Kantengewichte minimiert. Er ist die kostengünstigste Art, alle Knoten eines Netzes zu verbinden.

Wofür man ihn braucht

  • Netzwerk-Design: Strom-, Wasser- und Glasfasernetze so verlegen, dass alle Verbraucher angeschlossen sind und die Gesamtkosten minimal bleiben.
  • LAN-Verkabelung: Switches und Server mit möglichst wenig Kabelaufwand verbinden.
  • Cluster-Analyse: Ähnliche Datenpunkte über kurze Kanten zu Gruppen zusammenfassen.
  • Approximation: Der MST dient als Grundlage für Näherungslösungen schwierigerer Probleme wie dem Handlungsreisenden-Problem.

Kruskal-Algorithmus

1. Alle Kanten nach Gewicht aufsteigend sortieren
2. Mit der billigsten Kante beginnen
3. Jede Kante übernehmen, die keinen Zyklus erzeugt
   (Knoten befinden sich in verschiedenen Komponenten)
4. Stoppen, sobald n-1 Kanten gewählt sind (n = Knotenzahl)

Kruskal sortiert die Kanten zuerst mit einem Sortieralgorithmus und prüft Zyklen mit einer Union-Find-Struktur. Die Laufzeit liegt bei O(E log E) für E Kanten.

Prim-Algorithmus

1. Belieben Startknoten wählen und in den Baum aufnehmen
2. Solange noch Knoten fehlen:
   a. Billigste Kante vom aktuellen Baum zu einem
      noch nicht verbundenen Knoten wählen
   b. Kante und Knoten in den Baum aufnehmen

Prim wächst den Baum von einem Startknoten aus und wählt jede Runde die günstigste Verbindung nach außen. Mit einer Prioritätswarteschlange, typischerweise als Heap implementiert, erreicht er O(E log V). Er eignet sich besonders für dichte Graphen mit vielen Kanten.

Praxis-Tipps

  • Beide Algorithmen sind gierige Verfahren: Sie treffen lokal die beste Entscheidung und liefern trotzdem das globale Optimum — das garantiert die sogenannte Cut-Property.
  • Sind alle Kantengewichte verschieden, ist der minimale Spannbaum eindeutig.
  • Für die Implementierung reicht die Adjazenzmatrix oder Adjazenzliste des Graphen; gespeichert wird das Ergebnis als Baum.

Verwandte Grundlagen: Graph-Datenstruktur, Algorithmus, Dijkstra-Algorithmus (ebenfalls ein Graph-Algorithmus, aber für kürzeste Wege statt minimale Verbindungen).