Unser Beispiellabyrinth soll jetzt die folgende Form haben:
Wir nehmen an, wir rufen das Programm mit (Breitensuche 1 10 Graph) auf.
Anmerkungen: Der Graph ist hier nicht angegeben, lässt sich aber leicht bestimmen. Auch die Nachfolgerfunktion ist nicht angegeben, da sie sich von den vorigen nicht unterscheidet.
| 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))))
Die eigentliche Schleife ist wieder b-s, Breitensuche selbst nur die Aufrufhülle.
In b-s wird zunächst die lokale Variable wege-liste definiert und ihr der Wert ((1)) zugewiesen, also eine Liste, die allein die Liste mit dem Knoten 1 enthält.
Da weder die wege-liste leer ist, noch das Ziel zu den Nachfolgern des ersten Knoten des ersten Weges in der wege-liste =caar gehört, wird der else - Teil ausgeführt, in dem b-s sich endrekursiv mit dem Ergebnis der Expansion des aktuellen Weges aufruft.
Das ist hier nun ganz einfach: Es werden alle Kanten mit dem Knoten 1 als mögliche Wege erzeugt, also erhalten wir in der wege-liste ((2 1) (5 1))
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))))))