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.

Beschreibung des Algorithmus von Prim

Dieser Algorithmus startet mit einem beliebigen Knoten. Dieser wird markiert. Sukzessive werden an diesen Knoten weitere Knoten angebunden und so allmählich ein immer größerer Baum aufgebaut. Dabei wird derjenige Knoten dem Baum hinzugefügt, zu dem die kürzeste Kante vom bisherigen Baum führt. Diese Kante wird markiert.

Auch hier startet man damit, die Kanten nach ihrem Gewicht zu sortieren. Nun sucht man in dieser Liste nach einer Kante, bei der ein Knoten markiert ist und der andere nicht. Dabei kann man alle Kanten, bei denen beide Knoten markiert sind, streichen, da sie nie mehr gebraucht werden.

Hat man eine derartige Kante gefunden, wird sie markiert und aus der Liste entfernt. Der neu angebundene Knoten wird ebenfalls markiert. Diese Schritte wiederholt man, bis alle Knoten angebunden sind, also n-1 mal bei n Knoten.

Beispiel

1) Quelle https://de.wikipedia.org/wiki/Algorithmus_von_Prim, Bilder von Alexander Drichel, Lizenz CC-BY-SA 3.0

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.
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.