Prim Algorithmus

Der Prim Algorithmus wird genutzt, um den minimalen Spannbaum eines Graphen zu finden. Er kann in Graphen genutzt werden, die zusammenhängend, gewichtet und ungerichtet sind.

Dieses Kapitel bringt dir den Prim Algorithmus näher. Wir zeigen dir dabei, warum der Prim Algorithmus wichtig ist, was ihn ausmacht und wie er angewendet wird. Ob du dieses Wissen behalten hast, kannst du anschließend anhand unserer Übungsaufgaben überprüfen.

Synonym: Algorithmus von Prim

Warum ist der Prim Algorithmus wichtig?

Um Optimierungsprobleme im Rahmen des Operations Research in einem Unternehmen zu lösen, werden in vielen Fällen Algorithmen genutzt. Einer dieser Algorithmen ist der Prim Algorithmus. Er kann genutzt werden, um den kostengünstigsten Weg in einem Graphen zu ermitteln, mit dem alle Knoten eines Graphen miteinander verbunden werden können. Dies kann beispielsweise bei der Planung eines Logistik-Netzes nützlich sein.

Was versteht man unter dem Prim Algorithmus?

Ursprünglich entwickelt wurde der Prim Algorithmus im Jahr 1930 von dem Mathematiker Vojtěch Jarník aus der damaligen Tschechoslowakei. Wiederentdeckt 1957 von Robert C. Prim spricht man heutzutage in der Literatur aber vom Prim Algorithmus, nicht vom Algorithmus von Jarník.

Es handelt sich dabei um einen Algorithmus aus der Gruppe der Greedy Algorithmen, der in ungerichteten, gewichteten und zusammenhängenden Graphen den minimalen Spannbaum ermitteln kann. Unter dem minimalen Spannbaum eines Graphen versteht man den Teilgraph, der alle Knoten am kostengünstigsten miteinander verbindet.

Auch der Kruskal Algorithmus kann genutzt werden, um den minimalen Spannbaum eines Graphen zu ermitteln. Allerdings unterscheiden sich die beiden Algorithmen in ihrer Funktionsweise.

Der Kruskal Algorithmus startet mit allen Knoten des Graphen und betrachtet nacheinander die global günstigsten Kanten. Der Prim Algorithmus hingegen beginnt bei einem Knoten und fügt die jeweils günstigste Kante an dem aktuellen Knoten ein. Der Startpunkt kann dabei beliebig ausgewählt werden, da letztendlich alle Knoten im minimalen Spannbaum enthalten sein müssen.

Nach und nach wird immer die jeweils günstigste Kante des betrachteten Knoten eingefügt, also diejenige, welche das geringste Kantengewicht besitzt, um den nächsten Knoten zu verbinden.

Anwendung des Prim Algorithmus

Wie man den Prim Algorithmus anwendet, zeigen wir am folgenden Beispiel:

Gegeben ist der folgende Graph:

Zu diesem Graphen soll der minimale Spannbaum ermittelt werden. Dazu nutzen wir den Prim Algorithmus. Da der Startknoten beim Prim Algorithmus frei gewählt werden kann, entscheiden wir uns in unserem Beispiel für den Knoten B. Bei Betrachtung des Knoten B stellen wir fest, dass stellen wir fest, dass vier Kanten an diesem anliegen. Die kürzeste Kante ist die Kante BE mit einem Kantengewicht von 8.

Wir fügen diese Kante also unserem neuen Graphen hinzu:

Anschließend betrachten wir den Knoten E. Hier stellen wir fest, dass drei Kanten an dem Knoten anliegen. Die Kante mit dem geringsten Kantengewicht ist die Kante EC mit einem Gewicht von 4.

Demnach fügen wir also die Kante EC in unseren neuen Graphen ein:

Diese Schritte werden nun für die weiteren Knoten im Graphen wiederholt, bis alle Knoten durch die günstigsten Kanten miteinander verbunden sind.

So erhalten wir den minimalen Spannbaum des Graphen:

Übungsfragen