Prim-Algorithmus
Prim-Algorithmus Definition
Der Prim-Algorithmus löst folgendes Problem:
Ausgangspunkt
Man hat einen ungerichteten, zusammenhängenden, kantengewichteten Graphen; dieser besteht zum Beispiel aus ein paar Städten (Knoten), die durch in beide Richtungen befahrbare Straßen (ungerichtete Kanten) verbunden sind und diese Kanten sind mit Entfernungen oder Kosten gewichtet (kleinere Entfernungen oder Kosten sind besser).
Ziel / Ergebnis: minimaler Spannbaum
Der Prim-Algorithmus sucht dann den minimalen Spannbaum; das ist das Verbindungsnetz, mit dem alle Knoten (Städte) angesteuert werden zu insgesamt minimalen Kosten (geringstes gesamtes Kantengewicht, also kürzester möglicher Weg zwischen allen Knoten).
Alternative Begriffe: Algorithmus von Prim.
Beispiel
Beispiel: Prim-Algorithmus anwenden
Der Graph umfasst die 4 Knoten bzw. Städte Aachen, Berlin, Celle und Dortmund, die im folgenden mit ihren Anfangsbuchstaben abgekürzt werden.
Die Städte sind durch folgende Bahnstrecken oder Autobahnen (Kanten) mit hier fiktiven km -Angaben verbunden:
A – B: 200 km
A - C: 300 km
B - C: 250 km
B - D: 400 km
C - D: 350 km
Was ist der minimale Spannbaum, also das Verbindungsnetz, mit dem alle 4 Knoten zu minimalen Kosten besucht werden können?
Der Prim-Algorithmus löst das (auch für Hunderte von Städten und Verbindungen) in mehreren Iterationen (Durchgängen) so:
Beginn
Man beginnt mit einem beliebigen Knoten, zum Beispiel A.
Dieser wird in einer Liste der besuchten Knoten eingetragen:
Besuchte Knoten: {A}
Iteration 1
Nun betrachten wir von A ausgehend alle Kanten zu Knoten, die wir noch nicht besucht haben:
A – B: 200 km
A - C: 300 km
Wir wählen die Kante mit dem geringsten Kantengewicht (kürzeste Entfernung), das ist A - B mit 200 km und packen B in die Liste der besuchten Knoten:
Besuchte Knoten: {A, B}
Iteration 2
Nun betrachten wir von A und B ausgehend alle Kanten zu Knoten, die wir noch nicht besucht haben:
A - C: 300 km
B - C: 250 km
B - D: 400 km
Wir wählen die Kante mit dem geringsten Kantengewicht (kürzeste Entfernung), das ist B - C mit 250 km und packen C in die Liste der besuchten Knoten:
Besuchte Knoten: {A, B, C}
Iteration 3
Nun betrachten wir von A, B und C ausgehend alle Kanten zu Knoten, die wir noch nicht besucht haben:
B - D: 400 km
C - D: 350 km
Wir wählen die Kante mit dem geringsten Kantengewicht (kürzeste Entfernung), das ist C - D mit 350 km und packen D in die Liste der besuchten Knoten:
Besuchte Knoten: {A, B, C, D}
Ende
Alle Knoten sind besucht, der Algorithmus ist beendet.
Das gesamte Kantengewicht ist: 200 km (A - B) + 250 km (B - C) + 350 km (C - D) = 800 km.
Es gibt keinen Spannbaum, der alle Knoten einbezieht und eine geringere Gesamtstrecke hat.