Die MST-Heuristik

Schritt 3

Trifft man auf einen Knoten,der keine adjazenten Kanten zu einem unmarkierten Knoten besitzt (im Bild gelb markiert), läuft man solange zurück, bis man einen Knoten findet, der diese Eigenschaft erfüllt(im Bild Pink markiert).Jetzt sucht man wieder den kürzesten Pfad zu einem unmarkierten Knoten. Anschließend zieht man eine Kante(orange dargestellt) zwischen dem Knoten ohne ausweg(gelb) und dem neuen noch unmarkierten Knoten.

Schritt 3

  • Weiter
  • Zurück