Direkt zum Inhalt
  1. Startseite
  2. Quests
  3. #341

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ösung

Lösung anzeigen

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 .

Feedback geben

Hey! Ich bin Alexander FufaeV, der Physiker und Autor hier. Es ist mir wichtig, dass du stets sehr zufrieden bist, wenn du hierher kommst, um deine Fragen und Probleme zu klären. Da ich aber keine Glaskugel besitze, bin ich auf dein Feedback angewiesen. So kann ich Fehler beseitigen und diesen Inhalt verbessern, damit auch andere Besucher von deinem Feedback profitieren können.

Wie zufrieden bist Du?