Beispiel: Breitensuche Schritt für Schritt
Der Startknoten wird markiert (Distanz 0). Danach werden die Nachbarn in alphabetischer Reihenfolge entdeckt, in die Queue eingefügt und anschließend nacheinander abgearbeitet. Die große Zahl im Knoten zeigt die Distanz zum Start, die kleine rote Zahl zeigt die Abarbeitungsreihenfolge.
Übung: Trage Distanz und Reihenfolge selbst ein
Ziehe die passenden Zahlen-Chips per Drag&Drop auf die große (Distanz) bzw. kleine rote (Reihenfolge) Fläche im jeweiligen Knoten. Der golden umrandete Knoten ist der Startknoten. Sobald ein Knoten eine Distanz erhält, wird er blau (entdeckt). Sobald auch alle seine Nachbarn eine Distanz haben, wird er lila (abgearbeitet). Es muss nicht zwingend alphabetisch abgearbeitet werden – wichtig ist nur, dass die Reihenfolge zu den Distanzen passt.
Distanz-Chips
Reihenfolge-Chips
Beispiel: Der Entdeckungsbaum (BFS-Baum)
Links läuft die Breitensuche wie im ersten Beispiel ab. Rechts entsteht parallel der Entdeckungsbaum: Ein Knoten erscheint dort erst in dem Moment, in dem er entdeckt (in die Queue eingefügt) wird.
Graph
Entdeckungsbaum
Übung: Baue den Entdeckungsbaum
Links siehst du den Ausgangsgraphen zur Orientierung. Ziehe rechts die Knoten aus der Ablage auf den passenden Elternknoten im Baum, um sie anzuhängen. Die Wurzel (Startknoten) ist bereits fest vorgegeben.
Ausgangsgraph
Dein Entdeckungsbaum
Knoten-Ablage
Der BFS-Algorithmus mit Code
Beobachte, wann der Code einen Knoten in die Queue legt und wann er ihn als besucht markiert. Die markierte Zeile zeigt den aktuell ausgeführten Schritt.
Pseudocode
Übung: Wende den Algorithmus selbst an (Tiefensuche)
Der goldene Rahmen markiert den Startknoten. Erzeuge zuerst Stapel und Liste "besucht" einzeln über die Buttons. Danach ziehst du die Knoten aus der Ablage auf den Stapel bzw. auf „Besucht“. Entferne einen Stapelknoten mit dem kleinen x.
Knoten-Ablage
Stapel
Besucht
Übung: Zweite Variante der Tiefensuche
Bei dieser Variante wird ein Knoten bereits beim Ablegen auf dem Stapel als besucht markiert. Deshalb darf derselbe Knoten-Chip nacheinander in „Besucht“ und auf den Stapel gezogen werden. Hat der oberste Stapelknoten keinen unbesuchten Nachbarn mehr, entfernst du ihn mit dem kleinen x.
Knoten-Ablage
Stapel
Besucht
Beispiel: Tiefensuche Schritt für Schritt
Der Stapel arbeitet nach dem LIFO-Prinzip. Die markierte Pseudocode-Zeile zeigt den aktuellen Schritt.
Pseudocode
Übung: Trage die Abarbeitungsreihenfolge selbst ein
Ziehe die Zahlen-Chips auf die Reihenfolge-Felder der Knoten. Der goldene Rahmen markiert den Startknoten.
Reihenfolge-Chips
Beispiel: Der Entdeckungsbaum der DFS
Bei jedem Erstbesuch wird die zugehörige Entdeckungskante im Graphen rot. Rechts wächst gleichzeitig der entsprechende Entdeckungsbaum.
Graph
Entdeckungsbaum
Übung: Baue den DFS-Entdeckungsbaum
Klicke die Entdeckungskanten im Ausgangsgraphen in der richtigen Reihenfolge an. Korrekte Kanten werden rot markiert; rechts entsteht gleichzeitig der Entdeckungsbaum.