(defun breadth-first (graph start goal) (breadth-first-aux graph start goal (list (list start)))) (defun breadth-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 (breadth-first-aux graph start goal (append (rest path-queue) (new-paths path graph)) )))))となり, 再帰呼出をする際のpath-queueに渡す appendの引数の順をdepth-firstとは逆にするところだけが 違いになる.
> (breadth-first *graph1* 's 'f) (s d e f) > (breadth-first *graph1* 's 'e) (s d e) > (breadth-first *graph1* 'f 's) (f e d s) > (breadth-first *graph1* 's 'c) (s a b c)ここでもわかるように,縦型探索の場合には,すぐ近くに目標値があっても隣 接点リストの配置の如何によっては,遠回りの道が返る場合がありますが,横 型では,必ず一番短い道がでてくる.しかし,枝分かれが多い場合には,そ の道にたどり着くまでに時間がかかることになる.