(defun node-equal (a b) (equal a b)) (defun depth-first (graph start goal) (depth-first-aux graph start goal (list (list start)))) (defun depth-first-aux (graph start goal path-queue) (let ((path (first path-queue))) (cond ((null path-queue) nil) ((node-equal goal (first path)) (reverse path)) (t (depth-first-aux graph start goal (append (new-paths path graph) (rest path-queue)) )))))という具合に再帰的に定義をしたり,
(defun depth-first* (graph start goal) (let* ((path (list start)) (path-queue (list path))) (catch 'depth-first (while path-queue (cond ((node-equal goal (first path)) (throw 'depth-first (reverse path))) (t (setq path-queue (append (new-paths path graph) (rest path-queue))) (setq path (car path-queue))))))))というように繰り返し文で 定義することも可能です.
> (depth-first* *graph1* 's 'f) (s d e f) > (depth-first* *graph1* 'f 's) (f e b a s)以下のような実行結果が得られます.
> (setq *graph1* '((s a) (s d) (a b) (a d) (b c) (b e) (d e) (e f))) ((s a) (s d) (a b) (a d) (b c) (b e) (d e) (e f)) > (setq *graph2* '((f e) (e b) (e d) (d s) (d a) (c b) (b a) (a s))) ((f e) (e b) (e d) (d s) (d a) (c b) (b a) (a s)) > (depth-first *graph1* 's 'f) (s d e f) > (depth-first *graph2* 's 'f) (s a d e f) > (depth-first *graph1* 'f 's) (f e b a s) > (depth-first *graph2* 'f 's) (f e d a s) > (depth-first *graph1* 'd 's) (d s) > (depth-first *graph2* 'd 's) (d e b a s) > (depth-first* *graph1* 's 'f) (s d e f) > (depth-first* *graph2* 's 'f) (s a d e f) > (depth-first* *graph1* 'f 's) (f e b a s) > (depth-first* *graph2* 'f 's) (f e d a s) > (depth-first* *graph1* 'd 's) (d s) > (depth-first* *graph2* 'd 's) (d e b a s)*graph1*と*graph2*とでは,隣接点リストの順番が 異なることになるため返ってくるパスが異なっています. letとlet*の違いは,
> (setq a '(1 2 3 4 5 6)) (1 2 3 4 5 6) > (let ((a 1) (b a)) (list a b)) (1 (1 2 3 4 5 6)) > (let* ((a 1) (b a)) (list a b)) (1 1)