# `breadth_first_visit`

      template <class IncidenceGraph, class P, class T, class R>
      void breadth_first_visit(IncidenceGraph& G,
        typename graph_traits<IncidenceGraph>::vertex_descriptor s,
        const bgl_named_params<P, T, R>& params);

      template <class IncidenceGraph, class Buffer, class BFSVisitor, class ColorMap>
      void breadth_first_visit
        (const IncidenceGraph& g,
         typename graph_traits<IncidenceGraph>::vertex_descriptor s,
         Buffer& Q, BFSVisitor vis, ColorMap color)

この関数はカラー・マーカーがアルゴリズム中で初期化されない事を除けば 基本的に `breadth_first_search()` と同じである。 ユーザはアルゴリズムを呼ぶ前に全ての頂点の色が白色である事を確かめる責任が ある。この違いでグラフの型は Vertex List Graph である代わりに Incidence Graph である事のみが要求される。 更にこの違いはカラー・プロパティ・マップ中のより多くの柔軟性を考慮に入れて いる。例えば頂点上の部分的な関数を実装するだけのマップを使うことができる。 そしてそれは探索がグラフのごく一部にしか及ばない場合、より良い スペース効率である事ができる。

### Where Defined

`boost/graph/breadth_first_search.hpp`

### Parameters

IN: `IncidenceGraph& g`

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

IN: `vertex_descriptor s`

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

### Named Parameters

IN: `visitor(BFSVisitor vis)`

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

UTIL/OUT: `color_map(ColorMap color)`

> これはグラフを通る進行過程を保持するためにアルゴリズムによって使われる。 `ColorMap` の型は Read/Write Property Map のモデルでなければならなく、そのキー型はグラフの頂点記述子型 でなければならなく、カラー・マップの値型は ColorValue をモデルとしなければならない。
> デフォルト: `get(vertex_color, g)`

UTIL: `buffer(Buffer& Q)`

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

### Complexity

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

### 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()` に 加えて辺が木の辺でない場合に呼び出される。
- `vis.gray_target(e, g)` は `non_tree_edge()` に 加えて調査時点で終点が灰色に色づけされている場合に呼び出される。 灰色は頂点が現在キュー中にある印である。
- `vis.black_target(e, g)` は `non_tree_edge()` に 加えて調査時点で終点が黒色に色づけされている場合に呼び出される。 黒色は頂点がもはやキュー中にはない印である。
- `vis.finish_vertex(u, g)` は u の全ての出辺が 調べられ、全ての隣接頂点が発見された後で呼び出される。

### See Also

`breadth_first_search()`, `bfs_visitor`, and `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
最新版ドキュメント (英語)