1 | -- | 2 | -- | 3 | -- | 4 |
I | I | I | I | |||
5 | -- | 6 | -- | 7 | -- | 8 |
I | I | I | I | |||
9 | -- | 10 | -- | 11 | -- | 12 |
I | I | I | I | |||
13 | -- | 14 | -- | 15 | -- | 16 |
;;; ===== expandiere-Knoten ================================== (define (expandiere-Knoten wege-liste Graph) (let ((knoten (caar wege-liste)) (der-weg (car wege-liste))) (let loop ((die-Nachfolger (Nachfolger knoten Graph)) (akku ())) (cond ((null? die-Nachfolger) (append (cdr wege-liste) akku)) ((member (car die-Nachfolger) der-weg) (loop (cdr die-Nachfolger) akku)) (else (loop (cdr die-Nachfolger) (cons (cons (car die-Nachfolger) der-weg) akku))))))) ;;; ===== Breitensuche ======================================= (define (Breitensuche Start Ziel Graph) (let b-s ((wege-liste (list (list Start))))
... wird von diesen beiden Wegen der erste genommen und -da wieder weder die wege-liste leer ist, noch das Ziel zu den Nachfolgern des ersten Knoten des ersten Weges in der wege-liste gehört- dessen erster Knoten weiter expandiert.
Wichtig ist dabei zu beachten, dass die neu erzeugten Wege hinten an die wege-liste angehängt werden !
Die hat danach dann den Zustand: ((5 1) (3 2 1) (6 2 1)). Der Weg (1 2 1) fehlt natürlich, da die member - Abfrage in der Funktion expandiere-Knoten dies verhindert, damit Zyklen ausgeschlossen werden.
Im nächsten Schritt ...
(cond ((null? wege-liste) #f) ((member Ziel (Nachfolger (caar wege-liste) Graph)) (reverse (cons Ziel (car wege-liste)))) (else (b-s (expandiere-Knoten wege-liste Graph))))))