Algorithm 11（幅優先探索、BFS = Breadth-First-Search ）

• 入力：連結なグラフ $G$ と、その頂点 $v$
• 出力：$v$ を根とする $G$ の幅優先探索木 $T$

1. $v$ を要素とするキュー $Q=\{\,v\,\}$ を作り、$T$ の初期値は $v$ １点からなる木とする。
2. $Q$ の先頭から $x$ を取り出す。
3. 探索点 $x$ の未探索な隣接点のすべてを、番号の小さい順に $y_1$, $y_2$, $\cdots$, $y_s$ とする。
4. $Q$ の最後尾に $y_1$, $y_2$, $\cdots$, $y_s$ をこの順で追加し、 $T$ には辺 $xy_1$, $xy_2$, $\cdots$, $xy_s$ をすべて付加する。　
5. $Q$ が空(くう)リストになれば $T$ を出力して終了。そうでなければ 2°へ戻れ。

Ex.12　まずは二分木の場合に、チョー丁寧に動作を確認してみましょう。

　次のグラフで $v=0$ を根として幅優先探索を実行します。 1°　最初は $Q=\{\,0\,\}$, 赤い部分が $\require{color}\textcolor{red}{T}$ です。    $Q:0$ 2°　$Q$ の先頭から $\textcolor{blue}{x=0}$ を取り出し、これを 探索点（青い頂点）とします。 一旦 $Q$ は空になります。    $\require{cancel}Q:\cancel{0}$ 3°　探索点 $\textcolor{blue}{x=0}$ の隣接点 $1$, $2$ はどちらも未探索ですから $y_1=1$, $y_2=2$ です。

4°　$Q$ の最後尾に $y_1=1$, $y_2=2$ を追加、$\textcolor{red}{T}$ には辺 $\textcolor{red}{xy_1=01}$ と $\textcolor{red}{xy_2=02}$ を付加します。    $Q:\cancel{0},1,2$ 5°　$Q$ は空ではないので 2° へ戻ります。

2°　$Q$ の先頭から $\textcolor{blue}{x=1}$ を取り出し、これを探索点とします。    $Q:\cancel{0},\cancel{1},2$ 3°　探索点 $\textcolor{blue}{x=1}$ の隣接点 $0$, $3$, $4$ のうち未探索なのは $y_1=3$, $y_2=4$ の 2 つです。

4°　$Q$ の最後尾に $y_1=3$, $y_2=4$ を追加、$\textcolor{red}{T}$ には辺 $\textcolor{red}{xy_1=13}$ と $\textcolor{red}{xy_2=14}$ を付加します。    $Q:\cancel{0},\cancel{1},2\,,3\,,4$ 5°　$Q$ は空ではないので 2° へ戻ります。

2°　$Q$ の先頭から $\textcolor{blue}{x=2}$ を取り出し、これを探索点とします。    $Q:\cancel{0},\cancel{1},\cancel{2},3\,,4$ 3°　探索点 $\textcolor{blue}{x=2}$ の隣接点 $0$, $5$, $6$ のうち未探索なのは $y_1=5$, $y_2=6$ の 2 つです。

4°　$Q$ の最後尾に $y_1=5$, $y_2=6$ を追加、$\textcolor{red}{T}$ には辺 $\textcolor{red}{xy_1=25}$ と $\textcolor{red}{xy_2=26}$ を付加します。    $Q:\cancel{0},\cancel{1},\cancel{2},3\,,4\,,5\,,6$ 　未探索点が無くなりましたので人間がやるときはここでおしまいです。 （アルゴリズム的にはこのあと、$3$, $4$, $5$, $6$ を $Q$ から取り出して $Q$ が空になって終了します。）

Rem.13（ここ大事！） 自分が 探索点 $x$（青い頂点） に立っていて、 $x$ の隣接点までしか見ることができない、 というイマジネーションを働かせてください。

　Ex.12 ではそれぞれの場面で

$x=0$ のとき		$x=1$ のとき		$x=2$ のとき

しか見えていなくて、探索済み ( 赤い頂点 ) でない全ての頂点へ 幅広く 木を伸ばす、 と考えます。

※　慣れてくれば、キューを横に書くだけで作業できるようになります。

Ex.14　もうひとつ、木ではない次のグラフでやってみます。やはり $v=0$ を根とします。 1°　最初は $Q=\{\,0\,\}$, $\textcolor{red}{T}$ は $\textcolor{red}{0}$ の１点。    $Q:\textcolor{blue}{0}$ 2-3°　探索点 $\textcolor{blue}{x=0}$ の未探索隣接点は $y_1=2$, $y_2=5$.    $Q:\cancel{0}$ 4°　$Q$ に $2$, $5$ を追加、$\textcolor{red}{T}$ に $\textcolor{red}{02}$, $\textcolor{red}{05}$ を付加。    $Q:\cancel{0},\textcolor{blue}{2}\,,5$ 2-3°　探索点 $\textcolor{blue}{x=2}$ の未探索隣接点は $y_1=1$, $y_2=3$.    $Q:\cancel{0},\cancel{2},5$ 4°　$Q$ に $1$, $3$ を追加、$\textcolor{red}{T}$ に $\textcolor{red}{21}$, $\textcolor{red}{23}$ を付加。    $Q:\cancel{0},\cancel{2},\textcolor{blue}{5}\,,1\,,3$ 2-3°　探索点 $\textcolor{blue}{x=5}$ の未探索隣接点は $y_1=4$.    $Q:\cancel{0},\cancel{2},\cancel{5},1\,,3$ 4°　$Q$ に $4$ を追加、$\textcolor{red}{T}$ に $\textcolor{red}{54}$ を付加。    $Q:\cancel{0},\cancel{2},\cancel{5},\textcolor{blue}{1}\,,3\,,4$ 　未探索点が無くなったので終了です。