Aufgabe mit Lösung Algorithmus von Prim-Jarnik (Minimaler Spannbaum)
Wende den Algorithmus von Prim-Jarnik auf den abgebildeten Graph an, um einen minimalen Spannbaum zu bestimmen. Starte mit dem Knoten A.
Lösungstipps
Betrachte die Kanten zu den Nachbarknoten und wähle die günstigste Verbindung (Kante) aus.
Lösungen
Lösung
Start beim Knoten A. Nachbarknoten von A sind: {E}. Die günstigste Verbindung von A zu einem Nachbarknoten ist: 6. Das ist die Kante zwischen A zu E.
Bis jetzt betrachtete Knoten: {A}
Betrachte nun E. Nachbarknoten von E sind: {B, C}. Die günstigste Verbindung von E zu einem Nachbarknoten ist: 2. Das ist die Kante zwischen E und C.
Bis jetzt betrachtete Knoten: {A, E}
Betrachte nun C. Nachbarknoten von C sind: {E, D}. Die günstigste Verbindung von C zu einem Nachbarknoten ist: 3 (denn E wurde bereits betrachtet). Das ist die Kante zwischen C und D.
Bis jetzt betrachtete Knoten: {A, E, C}
Betrachte nun D. Nachbarknoten von D sind: {C, B}. Die günstigste Verbindung von D zu einem Nachbarknoten ist: 1. Das ist die Kante zwischen D und B.
Bis jetzt betrachtete Knoten: {A, E, C, D}
Betrachte nun B. Nachbarknoten von B sind: {D, E}. Beide Knoten wurden schon betrachtet.
Bis jetzt betrachtete Knoten: {A, E, C, D, B}
Alle Knoten wurden nun besucht. Der minimale Spannbaum ist hier die Verbindung zwischen A, E, C, D, B.