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