Alle Wege durchprobieren: der Suchbaum
Alle Wege durchprobieren: der Suchbaum
Um sicher den kürzesten Weg zu finden, kann man systematisch alle einfachen Wege vom Start zum Ziel aufschreiben und vergleichen. Übersichtlich geht das mit einem Suchbaum: Ganz oben steht der Start. Darunter stehen alle Nachbarn, zu denen man von dort gehen kann, darunter wieder deren Nachbarn – aber nur Knoten, die auf diesem Ast noch nicht vorkamen. Ein Ast endet am Ziel oder in einer Sackgasse. In Klammern steht die Länge des Weges bis dorthin.
Jeder Ast, der beim Ziel endet, ist ein Weg – hier zum Beispiel ABCD. Den kürzesten liest man an der kleinsten Zahl ab.
Noch ein Beispiel – Schritt für Schritt
Gesucht sind alle einfachen Wege von A nach D in diesem kleinen Graphen. Starte den Film mit ▶ oder gehe mit ⏮ und ⏭ Schritt für Schritt. Orange ist der Ast, an dem gerade gearbeitet wird – im Graphen und im Suchbaum.
Zwei Äste enden bei D: Das sind die beiden Wege ABD und ACBD. Der Ast ABC endet in einer Sackgasse: Von C aus sind alle Nachbarn auf diesem Ast schon besucht.
Im Suchbaum-Werkzeug der nächsten Aufgabe erklärt der Knopf ? die Bedienung.
Aufgabe 1: Erstelle den Suchbaum mit allen einfachen Wegen von A nach E. Jeder Ast endet bei E oder wenn kein unbesuchter Nachbar mehr erreichbar ist.
Ausgangsgraph
Aufgabe 1: Erstelle den Suchbaum mit allen einfachen Wegen von A nach E. Jeder Ast endet bei E oder wenn kein unbesuchter Nachbar mehr erreichbar ist.