next up previous
Next: 13.4 探索木表現のデータ変換 Up: 13 探索木 Previous: 13.2 目標頂点までの全パスを探索する

13.3 親子関係を表す木表現の生成

頂点の親(parent)から子(child)への関係を(parent . children)で表すとした 場合の探索木の記述を得るための関数は以下のgraph-treeのように定義できる． 
(defun graph-tree (graph start)
  (graph-tree-aux graph (list start)))

(defun graph-tree-aux (graph path)
  (let ((children (new-nodes path graph)))
    (if
      (null children)
      (cons (car path) nil)
      (cons
       (car path)
       (mapcar
        #'(lambda (x)
           (graph-tree-aux graph (cons x path)))
        children)))))
graph-tree は補助関数graph-tree-auxを使う形にしている．graph-tree-aux は，pathをもらい，そのパスの先端の頂点$P$が新しい頂点をもたなければ， その頂点のリストを返し，新しい頂点を持てば，その新しい頂点を新たなpath として再帰的に呼びだし，$P$を先頭にした木として返す． 
> (setq *tree2* (graph-tree *graph1* 's))
(s (d (e (b (a) (c)) (f))
      (a (b (e (f)) (c))))
   (a (d (e (b (c)) (f)))
      (b (e (f) (d)) (c))))
という具合になる．
generated through LaTeX2HTML. M.Inaba 平成18年5月7日