next up previous
Next: 7.3 縦型探索(depth-first search) Up: 7 グラフ探索 Previous: 7.1 パスの表現

7.2 パスの展開

グラフの探索においては，探索中の現在いる頂点（$v_n$）をもとに，$v_n$に 隣接している頂点を調べる．そこで，探索プログラムで必要となるも のとして，$v_1$から$v_n$までの path を与えて，$v_n$に隣接する頂点を求 めるという関数があげられる．この関数をnew-nodesと定義することにする． 次に，new-nodesで得られる頂点群へパスを伸ばして得られる新しいパス群を 作る関数をnew-pathsとして定義することにする． まず，new-nodesによりpathの最後の頂点$v_n$を展開するためには， (adjacency-list $v_n$ graph) として，頂点のリストを返す adjacency-list を用いる． 
(defun new-nodes (path graph)
  (new-nodes-aux
   path 
   (adjacency-list (first path) graph)))

(defun new-nodes-aux (path nodes)
  (cond
      ((null nodes) nil)
    ((node-member (car nodes) path)
     (new-nodes-aux path (cdr nodes)))
    (t (cons (car nodes)
             (new-nodes-aux path (cdr nodes))))))

(defun new-paths (path graph)
  (mapcar
   #'(lambda (n) (cons n path))
   (new-nodes path graph)))
new-nodesはpathをもらってpathの先頭の頂点（現在探索中の頂点） の隣接点リストを取りだし，隣接点リストの各頂点のうちpathに すでに含まれているものを取り除く．つまり，すでに通って来た 道にある頂点を除いた点のみを返す． new-pathsは，pathをもらって，それを伸ばしてゆく新しいpathを 生成する．new-nodesを用いてそれにより増える頂点の数だけの 新しいpathのリストが返される． 

> (new-nodes '(e d s) *graph1*)
(b f)

> (new-paths '(e d s) *graph1*)
((b e d s) (f e d s))

generated through LaTeX2HTML. M.Inaba 平成18年5月7日