# `undirected_dfs`

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

    // 名前無しパラメータバージョン
    template <typename Graph, typename DFSVisitor, typename VertexColorMap, typename EdgeColorMap>
    void undirected_dfs(const Graph& g, DFSVisitor vis, VertexColorMap vertex_color, EdgeColorMap edge_color)

    template <typename Graph, typename DFSVisitor, typename VertexColorMap, typename EdgeColorMap>
    void undirected_dfs(const Graph& g, DFSVisitor vis,
                        VertexColorMap vertex_color, EdgeColorMap edge_color,
                        typename graph_traits<Graph>::vertex_descriptor start)

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

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

辺は木と後退辺を明確にするための探索の間同様に色づけされる。

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

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

    DFS-VISIT(G, u)
      vcolor[u] := GRAY
      d_time[u] := time := time + 1
      for each e in Out[u]
        var ec := ecolor[e]
        ecolor[e] := BLACK
        if (vcolor[v] = WHITE)
          p[v] := u
          call DFS-VISIT(G, v)
        else if (vcolor[v] = GRAY and ec = WHITE)
          ...
      end for
      vcolor[u] := BLACK
      f_time[u] := time := time + 1
    -
    -
    頂点 u の初期化
    -
    -
    -
    -
    -
    -
    -
    頂点 s の開始
    -
    -
    頂点 u の開始
    -
    -
    -
    -
    頂点 u の発見
    -
    辺 (u,v) の調査
    -
    -
    (u,v) は木の辺
    -
    -
    (u,v) は後退辺
    -
    -
    頂点 u の終了
    -

### Where Defined

`boost/graph/depth_first_search.hpp`

### Parameters

IN: `Graph& g`

> 無向グラフ。グラフの型は Incidence Graph、Vertex List Graph、そして Edge List Graph のモデルでなければならない。

### Named Parameters

IN: `visitor(DFSVisitor vis)`

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

UTIL/OUT: `vertex_color_map(VertexColorMap vertex_color)`

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

UTIL: `edge_color_map(EdgeColorMap edge_color)`

> これは訪れられた辺の過程を保持するためにアルゴリズムによってつかわれる。 `EdgeColorMap` の型は Read/Write Property Map のモデルでなければならず、かつキー型はグラフの辺記述子型で なければならず、またカラー・マップの値型は ColorValue をモデルとしなければならない。
> デフォルト: なし

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.finish_vertex(u, g)` は出辺の全てが探索木に追加され、全ての隣接頂点が発見された (但しそれらの 出辺が調査される前に) 後の頂点において呼び出される。

### Example

例が `examples/undirected_dfs.cpp` 中にある。

### See Also

`depth_first_search`

### 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
最新版ドキュメント (英語)