# `depth_first_search`

    // 名前付きパラメータバージョン
    template <class Graph, class class P, class T, class R>
    void depth_first_search(Graph& G,
      const bgl_named_params<P, T, R>& params);

    // 名前無しパラメータバージョン
    template <class Graph, class DFSVisitor, class ColorMap>
    void depth_first_search(const Graph& g, DFSVisitor vis, ColorMap color)

    template <class Graph, class DFSVisitor, class ColorMap>
    void depth_first_search(const Graph& g, DFSVisitor vis, ColorMap color,
                            typename graph_traits<Graph>::vertex_descriptor start)

`depth_first_search()` 関数は有向グラフ中の頂点の深さ優先巡回を行う。 可能な時は、深さ優先巡回は次に訪れるために現在の頂点の隣接頂点を選ぶ。 もし全ての隣接頂点が既に発見されているならば、もしくは隣接頂点が存在しない ならば、アルゴリズムは未発見の隣接を持つ前の頂点へとバックトラックする。 一旦全ての到達可能な頂点が訪問されたら、アルゴリズムは残っている未発見の 頂点のどれかを選び出し、巡回を続ける。アルゴリズムは全ての頂点が訪問された 時に終了する。深さ優先探索はグラフ中の辺を分類するのと、頂点を順序づける のに役立つ。章 Depth-First Search は DFS の様々な特性を記述し、適当に例をあげている。

BFS に似て、頂点が発見された過程を保持するためにカラー・マーカーが使われる。 白色はまだ発見されていない頂点を印づけ、灰色は発見されたけれどもまだ未発見の 隣接している頂点を持つ頂点を印づける。黒い頂点はどの白い頂点にも隣接して いない発見された頂点である。

`depth_first_search()` 関数はアルゴリズムの内部で一定のイベント・ポイントにおいてユーザ定義のアクションを呼び出す。これは一般的な DFS アルゴリズムが 使用できる多くの状況に適用させるための機構を提供する。下の疑似コード中で、 DFS のためのイベント・ポイントは三角形と右側のラベルで示されている。 ユーザ定義のアクションはビジタ・オブジェクトの形で提供されなければならない。 すなわち、型が DFS Visitor の要求を満たして いるオブジェクトである。擬似コード中では、先行点を計算する アルゴリズムを p、発見時間を d、そして終了時間を t と 表す。デフォルトでは、`depth_first_search()` 関数はこれらのプロパティ を計算しない。しかしながらこれを実行するのに使える `predecessor_recorder` と `time_stamper` のようなあらかじめ 定義されたビジタが存在する。

    DFS(G)
      for each vertex u in V
        color[u] := WHITE
        p[u] = u
      end for
      time := 0
      if there is a starting vertex s
        call DFS-VISIT(G, s)
      for each vertex u in V
        if color[u] = WHITE
          call DFS-VISIT(G, u)
      end for
      return (p,d_time,f_time)

    DFS-VISIT(G, u)
      color[u] := GRAY
      d_time[u] := time := time + 1
      for each v in Adj[u]
        if (color[v] = WHITE)
          p[v] = u
          call DFS-VISIT(G, v)
        else if (color[v] = GRAY)
          ...
        else if (color[v] = BLACK)
          ...
      end for
      color[u] := BLACK
      f_time[u] := time := time + 1
    -
    -
    頂点 u の初期化
    -
    -
    -
    -
    頂点 s の開始
    -
    -
    頂点 u の開始
    -
    -
    -
    -
    頂点 u の発見
    -
    辺 (u,v) の調査
    -
    (u,v) は木の辺
    -
    -
    (u,v) は後退辺
    -
    (u,v) は交差辺または前方辺
    -
    頂点 u の終了
    -

### Where Defined

`boost/graph/depth_first_search.hpp`

### Parameters

IN: `Graph& g`

> 有向グラフ。グラフの型は Incidence Graph と Vertex List Graph のモデルでなければならない。

### Named Parameters

IN: `visitor(DFSVisitor vis)`

> アルゴリズムの内側で DFS Visitor コンセプトで指定されるイベント・ポイントで呼び出される ビジタ・オブジェクト。ビジタ・オブジェクトは値渡しされる [1]。
> デフォルト: `dfs_visitor<null_visitor>`

UTIL/OUT: `color_map(ColorMap color)`

> これはグラフを通る進行過程を保持するためにアルゴリズムによって使われる。 `ColorMap` の型は Read/Write Property Map のモデルでなければならず、かつキー型はグラフの頂点記述子型で なければならず、またカラー・マップの値型は ColorValue をモデルとしなければならない。
> デフォルト: サイズ `num_vertices(g)` の `default_color_type` の `std::vector` から作られた iterator_property_map で、添え字マップには `i_map` を用いる。

IN: `root_vertex(typename graph_traits<VertexListGraph>::vertex_descriptor start)`

> これは深さ優先探索が開始されるべき頂点を指定する。型は与えられたグラフの 頂点記述子型である。
> デフォルト: `*vertices(g).first`

IN: `vertex_index_map(VertexIndexMap i_map)`

> これは各頂点を `[0, num_vertices(g))` の範囲において整数にマップする。 このパラメータはデフォルトのカラー・プロパティ・マップが使われた時にのみ必要 である。`VertexIndexMap` の型は Readable Property Map のモデルでなければならない。マップの値型は汎整数型でなければなら ない。グラフの頂点記述子型はマップのキー型として使用できる必要がある。
> デフォルト: `get(vertex_index, g)`

### Complexity

時間複雑性は O(E + V) である。

### Visitor Event Points

- `vis.initialize_vertex(s, g)` はグラフの探索の開始前にグラフの各頂点で呼び出される。
- `vis.start_vertex(s, g)` は探索の開始前に始点において一度 呼び出される。
- `vis.discover_vertex(u, g)` は初めて頂点に出会った時に 呼び出される。
- `vis.examine_edge(e, g)` は各頂点のあらゆる出辺において、 それが発見された後に呼び出される。
- `vis.tree_edge(e, g)` は各辺において、それが探索木を構成 する辺のメンバになった時に呼び出される。もし先行点の記録を望むなら、 このイベント・ポイントで行いなさい。
- `vis.back_edge(e, g)` はグラフ中の後退辺において呼び出される。
- `vis.forward_or_cross_edge(e, g)` はグラフ中の前方辺または 交差辺において呼び出される。無向グラフ中ではこのメソッドは決して呼ばれない。
- `vis.finish_vertex(u, g)` は出辺の全てが探索木に追加され、 全ての隣接頂点が発見された (但しそれらの出辺が調査される前に) 後の頂点に おいて呼び出される。

### Example

`examples/dfs-example.cpp` 中の例は Figure 1 にある グラフへ適用された DFS を示す。

### See Also

`depth_first_visit` `undirected_dfs`

### Notes

[1] ビジタのパラメータは値渡しされるので、もしビジタが状態を持っているなら、 アルゴリズムの間のいかなる状態の変更も、送ったビジタ・オブジェクトには行われず ビジタ・オブジェクトのコピーに対して行われる。それゆえポインタまたは リファレンスによってこの状態をビジタに保持させる事を望むかもしれない。

Copyright © 2000-2001 | Jeremy Siek, Indiana University (jsiek@osl.iu.edu) Lie-Quan Lee, Indiana University (llee@cs.indiana.edu) Andrew Lumsdaine, Indiana University (lums@osl.iu.edu)

Japanese Translation Copyright © 2003 Takashi Itou
オリジナルの、及びこの著作権表示が全ての複製の中に現れる限り、この文書の複製、利用、変更、販売そして配布を認める。このドキュメントは「あるがまま」に提供されており、いかなる明示的、暗黙的保証も行わない。また、いかなる目的に対しても、その利用が適していることを関知しない。

このドキュメントの対象: Boost Version 1.30.0
最新版ドキュメント (英語)