(define
(Tiefensuche Start Ziel)
(let
t-s
((Alternativen (Nachfolger Start))
(besucht (list Start))
(stack ()))
(writeln Alternativen besucht stack) ; zum Protokollieren
(cond
Die Suche war erfolglos, wenn sowohl die Alternativen als auch der stack leer sind.
((and
(null? Alternativen)
(null? stack))
#f)
Gibt es keine Alternativen erfolgt der Rücksprung und der stack muss abgebaut werden.
((null? Alternativen)
(t-s
(car stack) ; stellt Alternativen (bis auf 1.) wieder her
(cdr besucht) ; stellt besucht - Liste wieder her
(cdr stack))) ; stellt stack wieder her
Hier waren wir schon. Alternativen abbauen !
((member (car Alternativen) besucht)
(t-s
(cdr Alternativen)
besucht
stack))
Das Ziel ist gefunden !
((eq? (car Alternativen) Ziel)
(writeln (reverse (cons (car Alternativen) besucht)))
#t)
Ab in die Tiefe !
(else
(t-s
(Nachfolger (car Alternativen))
(cons (car Alternativen) besucht)
(cons (cdr Alternativen) stack))))))
(define
(Nachfolger Element)
(cadr (assoc Element Graph)))