Direkt zum Inhalt
  1. Startort
  2. Quests
  3. 📖
Level 2
Level 2 setzt Schulmathematik voraus. Geeignet für Schüler.

Aufgabe mit Lösung Algorithmus von Prim-Jarnik (Minimaler Spannbaum)

Ein ungerichteter zyklischer Graph mit gewichteten Kanten

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.

Details zum Inhalt
  • Die Quest wurde hinzugefügt von FufaeV am .
  • Die Quest wurde aktualisiert von FufaeV am .