zurück nächste

Der Ablauf einer Breitensuche am Beispiel


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))))))