;;; ===== expandiere-Knoten ==================================
; Der erste Weg wird aus der Wegeliste entnommen, aus dem
; Graphen die Liste der Wege geholt, zu denen eine Verbindung
; führt und es werden die gefundenen neuen Wege an die
; wege-liste angehängt.
; wege-liste --> '((3 2 1) (5 4 1) ...)
; = Prinzip der Warteschlange.
(define
(expandiere-Knoten wege-liste Graph)
(let
((knoten (caar wege-liste)) ;{1}
(der-weg (car wege-liste)))
(let
loop
((die-Nachfolger (Nachfolger knoten Graph))
(akku ()))
(cond
((null? die-Nachfolger) ;{2}
(append (cdr wege-liste) akku))
((member (car die-Nachfolger) der-weg) ;{3}
(loop (cdr die-Nachfolger) akku))
(else ;{4}
(loop
(cdr die-Nachfolger)
(cons
(cons
(car die-Nachfolger)
der-weg)
akku)))))))
;{1} knoten ist der erste Koten aus dem ersten Weg, der in der
; wege-liste abgelegt ist.
;{2} Wenn es überhaupt noch Nachfolger des aktuellen Knoten
; gab, sind sie jetzt dem Weg jeweils hinzugefügt worden,
; in akku abgelegt und müssen nun hinten an die wege-
; liste angehängt werden.
;{3} Ist der aktuelle Nachfolgeknoten schon in der wege-liste
; enthalten, ist ein Zyklus gefunden und der neue Weg wird
; nicht in akku übernommen.
;{4} Anderenfalls wird der um den Knoten verlängerte Weg dem
; akku hinzugefügt.
;;; ===== Breitensuche =======================================
; Die Funktion Breitensuche selbst muss nun nur noch die
; Steuerung der o.a. Funktion erledigen.
(define
(Breitensuche Start Ziel Graph)
(let
loop
((wege-liste (list (list Start))))
(cond
((null? wege-liste) #f)
((member Ziel (Nachfolger (caar wege-liste) Graph))
(reverse (cons Ziel (car wege-liste))))
(else
(loop
(expandiere-Knoten wege-liste Graph))))))