BFSツリー

BFSツリーは、始点から辺数の近い頂点を層ごとに訪問するグラフ探索である。

仕組み

始点をキューへ入れ、dequeueした頂点の未訪問隣接頂点を訪問済みにしてenqueueする。

計算量・性質

隣接リストではO(V+E)、訪問集合とキューにO(V)。

具体例

無重みグラフでは最初に到達した距離が始点からの最短辺数になる。

限界と注意点

重み付き最短路にはそのまま使えず、訪問済みをenqueue時に付けないと重複が増える。