Prim konstruiert einen Minimum Spanning Tree eines gewichteten, ungerichteten, zusammenhängenden Graphen.
Ziel ist nicht der kürzeste Weg von einer Quelle, sondern die minimale Gesamtsumme aller ausgewählten Kanten.
Grundidee
Von einem Startknoten aus wird der Baum schrittweise erweitert.
Immer wird die leichteste Kante gewählt, die einen bereits aufgenommenen Knoten mit einem neuen Knoten verbindet.
Cut Property
Die Korrektheit basiert auf der Cut Property:
Die leichteste Kante über einen Cut kann Bestandteil eines MST sein.
Prim vs Kruskal
Prim erweitert einen zusammenhängenden Baum.
Kruskal sortiert Kanten global und verwendet Union-Find.
Prim vs Dijkstra
Prim minimiert die Gesamtkosten des Spannbaums.
Dijkstra minimiert Distanzen von einer Quelle.
Negative Gewichte
Negative Kantengewichte sind für MST erlaubt.
Disconnected Graph
Ist der Graph nicht zusammenhängend, entsteht statt eines MST ein Minimum Spanning Forest.
Anwendungen
- Kabel- und Glasfasernetze
- Infrastruktur
- Sensor-Netzwerke
- Data-Center-Backbones
- Utility-Netze
Komplexität
Adjazenzliste + Heap:
O(E log V)Adjazenzmatrix:
O(V²)Fazit
Prim ist eine zentrale Greedy-Methode für kostenminimale Verbindungen in gewichteten ungerichteten Graphen.