Dies ist eine alte Version des Dokuments!
Algorithmus von Prim
(A1)
Untersuche im Graphentester den Algorithmus "MST (Prim)" zur Bestimmung des minimalen Spannbaums mit der Insel-Karte (04_inseln.csv im Ordner 08_minimalspanningtree).
- Versuche herauszufinden, wie der Algorithmus funktioniert, indem du ihn Schritt für Schritt ausführst.
- Welche Situation muss vermieden werden? Fällt dir dafür eine einfache Lösung ein.
- Beschreibe deinen so gefundenen Algorithmus in einem kurzen Text.
- Vergleiche deine Beschreibung mit den Musterlösung (unten) und bewerte, ob du das Vorgehen richtig nachvollzogen hast.
Beispiel
Dies ist der Graph, zu dem der Algorithmus von Prim einen minimalen Spannbaum berechnet. Die Zahlen bei den einzelnen Kanten geben das jeweilige Kantengewicht an.
{{ 300px-prim_algorithm_1.svg.png?220 |}}
Als Startknoten für den Spannbaaum T wird der Knoten D gewählt. (Es könnte auch jeder andere Knoten ausgewählt werden.)
Mit dem Startknoten können die Knoten A,B,E und F jeweils unmittelbar durch die Kanten DA, DB, DE und DF verbunden werden.
Unter diesen Kanten ist DA diejenige mit dem geringsten Gewicht und wird deshalb zusammen mit dem Knoten A zum Graphen T hinzugefügt.
 |
|
 | |
 | |
 |
|
 | |
 | |
1)
Quelle https://de.wikipedia.org/wiki/Algorithmus_von_Prim, Bilder von Alexander Drichel, Lizenz CC-BY-SA 3.0