vorige nächste Programm

Der Algorithmus von Prim


Der Algorithmus von Prim
Beginne mit einem Baum, der allein aus einer Ecke besteht.
Ordne alle Kanten von dieser Ecke aus nach ihren Kosten. (->Prioritätswarteschlange nach den Bewertungen)
Füge nun jeweils immer aus dieser jeweils die nächste Kante mit den geringsten Kosten ein, die keinen Zyklus erzeugt. Dann füge alle von der freien Ecke ausgehenden zulässigen Kanten in die Prioritätswarteschlange ein.
Brich damit ab, wenn alle Ecken (Knoten) des Graphen zum Baum gehören.

Auch hier kann man sehr leicht zeigen, dass der hier beschriebene Algorithmus eine Lösung findet, wenn es überhaupt Lösungen geben kann. Wir sehen uns hier ebenso einmal den Aufbau des Baumes für ein Beispiel an. Beim Algorithmus von Prim sind die beim Aufbau des Baumes entstehenden Teilgraphen stets zusammenhängend. Wird eine Kante hinzugefügt, dann hat sie stets eine Ecke mit dem derzeitigen Teilgraphen gemeinsam, setzt also einen Ast fort oder bildet einen neuen.

Bemerkenswert für unsere Betrachtung verschiedener Suchverfahren ist die Feststellung:

Die Datenstruktur ändert sich!

Mit dem völlig neuen Ansatz zur Lösung des Problems benötigen wir auch eine völlig neue Datenstruktur: Es wird eine Datenstruktur aufgebaut, in der die Elemente nicht wie bei stack (->Tiefensuche) und queue (Warteschlange ; ->Breitensuche) nach dem Zeitpunkt ihres Einfügens in die Datenstruktur geordnet werden, sondern sie werden nach dem ihnen zugehörigen Wert geordnet eingefügt (oder es wird zumindest die Zugriffsfunktion so realisiert, dass der Zugriff so funktioniert, als wäre das so).

Die angemessene Datenstruktur zur Lösung des Problems ist die Prioritäts - Warteschlange.

Das Programm ist wegen der Behandlung der Prioritätswarteschlange etwas umfangreicher als das zum Algorithmus von Kruskal. Hier wird außerdem eine grafische Darstellung mit bereitgestellt.

Bild zum minimal spanning tree