zurück Programmablauf
;;; ===== 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))))))