# `breadth_first_search`

    // 名前付きパラメータバージョン
    template <class VertexListGraph, class P, class T, class R>
    void breadth_first_search(VertexListGraph& G,
      typename graph_traits<VertexListGraph>::vertex_descriptor s,
      const bgl_named_params<P, T, R>& params);

    // 名前無しパラメータバージョン
    template <class VertexListGraph, class Buffer, class BFSVisitor,
    	  class ColorMap>
    void breadth_first_search(const VertexListGraph& g,
       typename graph_traits<VertexListGraph>::vertex_descriptor s,
       Buffer& Q, BFSVisitor vis, ColorMap color);

`breadth_first_search()` 関数は有向グラフまたは無向グラフの幅優先巡回 [49] を行う。幅優先巡回は、 始点から遠方に離れた頂点を訪れる前に近い頂点を訪れる。 この文脈中で“距離”とは始点からの最短経路中の辺の数として定義される。 `breadth_first_search()` 関数は始点から全ての到達可能な頂点への 最短経路を計算するのに使用でき、結果として最短経路の距離が得られる。 BFS に関連した更なる定義は章 Breadth-First Search を見よ。

BFS は巡回を実装するのに二つのデータ構造を使っている: 各頂点のカラー・マーカー とキューである。白色の頂点は未発見で、一方灰色の頂点は発見されたけれども 未発見の隣接頂点を持つ。黒色の頂点は発見されており、他の黒色もしくは灰色の 頂点にのみ隣接している。アルゴリズムは頂点 u をキューから取り除き、 各出辺 (u,v) を調べながら進められる。もし隣接頂点 v がまだ 未発見ならば、灰色に色づけしてキューに置く。すべての出辺を調べた後、 頂点 u を黒色に色づけして手順を繰り返す。BFS アルゴリズムの疑似コード を下に示す。

    BFS(G, s)
      for each vertex u in V[G]
        color[u] := WHITE
        d[u] := infinity
        p[u] := u
      end for
      color[s] := GRAY
      d[s] := 0
      ENQUEUE(Q, s)
      while (Q != Ø)
        u := DEQUEUE(Q)
        for each vertex v in Adj[u]
          if (color[v] = WHITE)
            color[v] := GRAY
            d[v] := d[u] + 1
            p[v] := u
            ENQUEUE(Q, v)
          else
            if (color[v] = GRAY)
              ...
            else
              ...
        end for
        color[u] := BLACK
      end while
      return (d, p)
    頂点 u の初期化

    頂点 s の発見

    頂点 u の調査
    辺 (u,v) の調査
    (u,v) は 木の辺

    頂点 v の発見
    (u,v) は 木でない辺

    (u,v) は灰色の終点を持つ

    (u,v) は黒色の終点を持つ

    頂点 u の終了

`breadth_first_search()` 関数は一定のイベント・ポイントと呼ばれる、 ユーザ定義のアクションで拡張する事ができる。アクションはビジタ・オブジェクトの 形で提供されなければならない。すなわち、型が BFS Visitor の要求を満たしているオブジェクトであ る。上の擬似コード内で、イベント・ポイントは右側のラベルである。更に各 イベント・ポイントの記述を以下に示した。デフォルトでは `breadth_first_search()` 関数はどんなアクションも実行しない。距離や 先行点の記録さえも。しかしながらこれらは `distance_recorder` と `predecessor_recorder` のイベント・ビジタを用いて容易に追加できる。

### Where Defined

`boost/graph/breadth_first_search.hpp`

### Parameters

IN: `VertexListGraph& g`

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

IN: `vertex_descriptor s`

> 探索が開始される始点。

### Named Parameters

IN: `visitor(BFSVisitor vis)`

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

UTIL/OUT: `color_map(ColorMap color)`

> これはグラフを通る進行過程を保持するためにアルゴリズムによって使われる。 アルゴリズムは開始時に全ての頂点の色を白色に初期化するため、ユーザは `breadth_first_search()` を呼ぶ前にカラー・マップを初期化する必要はない。もし複合的な幅優先探索をグラフ上で行う必要があるなら (例えばいくつかの 切断された成分があるなら) `breadth_first_visit()` 関数を 使って独自の初期化を行いなさい。

> `ColorMap` の型は Read/Write Property Map のモデルでなければならなく、そのキー型はグラフの頂点記述子型でなければならな く、カラー・マップの値型は ColorValue をモデルとしなければならない。
> デフォルト: サイズ `num_vertices(g)` の `default_color_type` の `std::vector` から作られた iterator_property_mapで、添え字マップには `i_map` を用いる。

IN: `vertex_index_map(VertexIndexMap i_map)`

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

UTIL: `buffer(Buffer& Q)`

> 頂点が発見される順序を決定するために使用されるキュー。もしFIFO キューが使われ ると、 巡回は通常の BFS 順序付けに従う。他の型のキューも使用できるが、巡回順序は異な る。例えば Dijkstra のアルゴリズムは優先度付きキューを用いて実装 する事ができる。`Buffer` の型は Buffer のモデルでなければならない。buffer の `value_type` はグラフの `vertex_descriptor` 型でなければならない。
> デフォルト: `boost::queue`

### Complexity

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

### Visitor Event Points

- `vis.initialize_vertex(v, g)` は探索の開始前に各頂点で呼び出される。
- `vis.examine_vertex(u, g)` は各頂点においてそれがキューから削除される時に呼び出される。
- `vis.examine_edge(e, g)` は各頂点のあらゆる出辺において、頂点が キューから削除された後で直ちに呼び出される。
- `vis.tree_edge(e, g)` は `examine_edge()` に加えて 辺が木の辺の場合に呼び出される。辺 `e` の終点はこの時に 発見される。
- `vis.discover_vertex(u, g)` はアルゴリズムが初めて 頂点 u に出会った時に呼び出される。始点に近い全ての頂点が 発見されており、始点から遠方に離れた頂点はまだ発見されていない。
- `vis.non_tree_edge(e, g)` は `examine_edge()` に加え て辺が tree edge でない場合に呼び出される。
- `vis.gray_target(e, g)` は `non_tree_edge()` に加えて 調査時点で終点が灰色に色づけされている場合に呼び出される。灰色は頂点が現在 キュー中にある印である。
- `vis.black_target(e, g)` は `non_tree_edge()` に加え て調査時点で終点が黒色に色づけされている場合に呼び出される。黒色は頂点がもはや キュー中にはない印である。
- `vis.finish_vertex(u, g)` は u の全ての出辺が 調べられ、全ての隣接頂点が発見された後で呼び出される。

### Example

`example/bfs-example.cpp` 中にある例は、Figure 5 のグラフにおいて BGL 幅優先探索アルゴリズムを用いて実演している。 `example/bfs-example2.cpp` のファイルは同じ例を含むが、使われている `adacency_list` クラスは `VertexList`を持っており、`EdgeList` が `listS` に 置かれている。

### See Also

`bfs_visitor` と `depth_first_search()`

### Notes

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

Copyright © 2000-2001 | Jeremy Siek, Indiana University (jsiek@osl.iu.edu)

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

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