Inhaltsverzeichnis
In diesem Kurstext behandeln wir den Algorithmus von Prim, welcher einen minimalen Spannbaum für ungerichtete, kantengewichtete und zusammenhängend endlichen Graphen ermittelt.
Beim Prim-Algorithmus wird von einem zufälligen Punkt ausgehend jeweils die nächste Kante mit dem niedrigsten Kantengewicht hinzugefügt, bis ein minimaler Spannbaum entsteht.
Der Prim-Algorithmus gehört zu den Greedy Algorithmen der Graphentheorie.
Merke
Greedy-Algorithmen zeichnen sich dadurch aus, dass sie schrittweise denjengen Folgezustand auswählen, der zum Zeitpunkt der Wahl das beste Ergebnis verspricht.
Der tschechische Mathematiker Vojtěch Jarník entwickelte im Jahr 1930 den Prim-Algorithmus, dieser wurde jedoch im Jahr 1957 vom Mathematiker Robert C. Prim wiederentdeckt.
Beispiel: Prim-Algorithmus
Zum besseren Verständnis betrachten wir als nächstes ein Beispiel zum Prim-Algorithmus.
Gegeben sei der folgende ungerichtete, gewichte und zusammenhängend endliche Graph:
Beispiel
Bestimme den minimalen Spannbaum mittels Prim-Algorithmus. Starte im Knoten A!
Beim Prim-Algorithmus startet man an einem bliebigen oder vorgegebenen Knoten (hier: Knoten A). Von diesem Knoten ausgehend wird die Kante mit dem niedrigsten Kantengewicht ausgewählt. Bei mehreren Kanten mit demselben Kantengewicht, kann die Auswahl beliebig erfolgen. Es dürfen nur Kanten berücksichtigt werden, die nicht zwei bereits abgefahrene Knoten miteinander verbinden.
Merke
Im Gegensatz zum Kruskal-Algorithmus terminiert der Prim-Algorithmus, wenn alle Knoten enthalten sind. Der Kruskal-Algorithmus terminiert, wenn alle Kanten abgefahren sind.
Wir beginnen in diesem Beispiel mit dem Knoten A. Ist kein Startknoten vorgegeben, so kann beliebig gewählt werden. Von diesem Knoten ausgehend wird die Kante mit dem niedrigsten Kantengewicht gewählt.
1. An den Knoten A sind drei Kanten AB, AC und AD angeschlossen.
2. Wir wählen die Kante mit dem kleinsten Kantengewicht aus, in diesem Fall AC. Wir markieren die Kante und die beiden Knoten A und C.
3. Wir haben nun zwei Knoten gegeben, mit den Kanten AB, AD, CF und CD. Wir wählen die Kante CD mit dem Kantengewicht 1 aus. Wir markieren die Kante und den Knoten D.
4. An die drei markierten Knoten sind die Kanten AB, AD, CF und DB angeschlossen. Die Kante AD dürfen wir nicht wählen, weil diese bereits zwei markierte Knoten verbindet. Es verbleiben also die Kanten AB, CF und DB. Wir wählen DB mit dem Kantengewicht 2.Wir markieren die Kante und den Knoten D.
5. Es stehen die Kanten AB, CF, DE, DF, DG und DH zur Auswahl. Die Kante AB darf nicht zugefügt werden, da diese bereits zwei markierte Knoten verbindet. Wir können uns beliebig zwischen den Kanten DE und DG mit den Kantengewichten 6 entscheiden und wählen DE. Wir markieren die Kante und den Knoten E.
6. Die Kanten CF, DF, DG, DH und EH stehen zur Auswahl. Wir wählen die Kante DG mit den Kantengewicht 6. Wir markieren die Kante und den Knoten G.
7. Zur Auswahl stehen die Kanten CF, DF, DH, EH, GF und GH. Wir wählen die Kante GH mit dem Kantengewicht 1. Wir markieren die Kante und den Knoten H.
8. Die Kanten CF, DF, DH, EH und GF stehen zur Auswahl. Die Kanten DH und EH dürfen nicht gewählt werden, da sie zwei bereits markierte Knoten verbinden. Wir wählen die Kante GF mit dem Kantengewicht 3 und markieren Kante und Knoten F.
Der Algorithmus terminiert, da alle Knoten markiert sind. Der minimale Spannbaum ergibt sich aus den grün markierten Kanten:
Weitere interessante Inhalte zum Thema
-
Maschensatz, 2. Kirchhoffsches Gesetz
Vielleicht ist für Sie auch das Thema Maschensatz, 2. Kirchhoffsches Gesetz (Gleichstrom) aus unserem Online-Kurs Elektrotechnik interessant.
-
Schweißen
Vielleicht ist für Sie auch das Thema Schweißen (Formgebung der Werkstoffe) aus unserem Online-Kurs Werkstofftechnik 2 interessant.
