# **Tiefensuche** :arrow_down: ## Erklärung :exploding_head: Unser Labyrinth bestehe aus Kreuzungen und Gängen. * ein Haken für bereits einmal durchlaufene Gänge * zwei Haken für „tote“ Gänge * Sackgasse -> dreht man um und zurück zur letzten Kreuzung * Beim Erreichen einer Kreuzung malt man einen Haken/Zahl um sich später zu erinnern --- Anschließend gibt es mehrere Möglichkeiten: * ein Haken/Zahl = umdrehen * kein Haken = in den ersten Gang von links gehen und makieren * alle Gängen einen Haken/Zahl = in den mit einem Haken/zahl gehen * alle Gängen zwei Haken/Zahlen = am Start oder keinen Ausgang --- ## Quellcode :robot_face: 1.  function Tiefensuche(X)    2. if Zustand[X] = "entdeckt" then return    3. if X = Ziel then exit {Ziel gefunden!} 4. Zustand[X] := "entdeckt"    5. for each benachbarte Kreuzung Y von X do    6. Tiefensuche(Y)    7. endfor    8. end --- ## Beispiel :label: Start A Richtung Norden. Die erste Kreuzung ist C. 1 : eine Markierung am Südausgang von C machen 2 : markieren und nach links gehen B : Sackgasse –> also umdrehen. C: nach links, da erster Gang ohne Markierung  --- E: unberührte Kreuzung -> nach links gehen und markieren --- 6: den zwei Kurven folgen G: unberührte Kreuzung -> Kreuzung gerade überqueren H: Sackgasse -> also umdrehen 9: zurückgehen bis Kreuzung G!  --- G: links unmarkiert -> links gehen E: Regel gegen das Im-Kreis-Laufen -> umdrehen G: links geringste Markierung -> links gehen  --- 15: den Kurven folgen E: nördlicher Teil abgesucht -> Osten ohne Markierung -> gehen F: Ziel erreicht  --- ## Anwendungen :dart: * nicht nur für Labyrinthe * Informationen, welche Zusammenhängen bilden (Wikepdialinks) * da durch Tiefensuche nicht im Kreis gesucht wird