組合せとグラフの理論(塩田)第6回 (3) 幅優先探索
幅優先探索のアルゴリズム
教科書では p.79 で簡単に書いてありますが、大事なアルゴリズムですので時間を掛けてやりましょう。
「根 ( root )」と呼ばれる頂点を与えて、その根から
幅広く 木を伸ばしてゆき、全域木を作ります。
Algorithm 11(幅優先探索、BFS = Breadth First Search )
- 入力:連結なグラフ $G$ と、その頂点 $v$
- 出力:$v$ を根とする $G$ の幅優先探索木 $T$
- $v$ を要素とするキュー $Q=\{\,v\,\}$ を作り、$T$ の初期値は $v$ 1点からなる木とする。
- $Q$ の先頭から $x$ を取り出す。
- 探索点 $x$ の未探索な隣接点のすべてを、番号の小さい順に
$y_1$, $y_2$, $\cdots$, $y_s$
とする。
- $Q$ の最後尾に $y_1$, $y_2$, $\cdots$, $y_s$ をこの順で追加し、
$T$ には辺 $xy_1$, $xy_2$, $\cdots$, $xy_s$ をすべて付加する。
- $Q$ が空(くう)リストになれば $T$ を出力して終了。そうでなければ 2°へ戻れ。
3°の「未探索な隣接点のすべて」というところが「幅広く」ということです。
例題
$\require{color}$
Ex.12
入力を
$G=$
, $v=0$ とします。
-
$0$ を探索済みとし、
$T=$ ,
$Q=\{\,\textcolor{blue}{0}\,\}$ .
( 青い頂点 は $Q$ の先頭で、次の現在地になります。)
-
$Q$ の先頭から $\textcolor{blue}{x=0}$ を取り出して現在地とし、$Q=\emptyset$ .
-
現在地 $\textcolor{blue}{x=0}$ の未探索な隣接点は $y_1=2$, $y_2=4$ のふたつ。
-
$y_1=2$, $y_2=4$ を探索済みとして $Q$ の最後尾に追加し $Q=\{\,\textcolor{blue}{2},\,4\,\}$,
$T$ には辺 $xy_1=02$ と $xy_2=04$ を付加して
$T=$ .
-
$Q$ の先頭から $\textcolor{blue}{x=2}$ を取り出して現在地とし、$Q=\{\,4\,\}$ .
-
現在地 $\textcolor{blue}{x=2}$ の未探索な隣接点は $y_1=3$ .
-
$y_1=3$ を探索済みとして $Q$ の最後尾に追加し $Q=\{\,\textcolor{blue}{4},\,3\,\}$ ,
$T$ には辺 $xy_1=23$ を付加して
$T=$ .
-
$Q$ の先頭から $\textcolor{blue}{x=4}$ を取り出して現在地とし、$Q=\{\,3\,\}$ .
-
現在地 $\textcolor{blue}{x=4}$ の未探索な隣接点は $y_1=1$ .
-
$y_1=1$ を探索済みとして $Q$ の最後尾に追加し $Q=\{\,\textcolor{blue}{3},\,1\,\}$ ,
$T$ には辺 $xy_1=41$ を付加して
$T=$ .
手でやるときは、未探索点が無くなったのでここで終了すればよく、
$T=$
となります。( アルゴリズム的には、このあと $Q$ から $3$, $1$ が取り出されて $Q=\emptyset$ となって終了します。)
手順を表にしてまとめておくと
現在地 $x$ | $x$ の未探索な隣接点 | 探索木 $T$ に付加する辺 | キュー $Q$ |
| | | $\textcolor{white}{,}\textcolor{blue}{0}\textcolor{white}{,}$ |
$\textcolor{blue}{0}\textcolor{white}{,}$ | $2$, $4$ | $02$, $04$ | $\textcolor{blue}{2}$, $4$ |
$\textcolor{blue}{2}\textcolor{white}{,}$ | $3$ | $23$ | $\textcolor{blue}{4}$, $3$ |
$\textcolor{blue}{4}\textcolor{white}{,}$ | $1$ | $41$ | $3$, $1$ |
Ex.12'
入力を同じグラフ
$G=$
とし、根を $v=1$ とすると、手順は
現在地 $x$ | $x$ の未探索な隣接点 | 探索木 $T$ に付加する辺 | キュー $Q$ |
| | | $\textcolor{white}{,}\textcolor{blue}{1}\textcolor{white}{,}$ |
$\textcolor{blue}{1}\textcolor{white}{,}$ | $3$, $4$ | $13$, $14$ | $\textcolor{blue}{3}$, $4$ |
$\textcolor{blue}{3}\textcolor{white}{,}$ | $2$ | $32$ | $\textcolor{blue}{4}$, $2$ |
$\textcolor{blue}{4}\textcolor{white}{,}$ | $0$ | $40$ | $3$, $0$ |
となり、幅優先探索木は
$T=$
となります。
Ex.12''
三たび同じグラフ
$G=$
で、根を $v=2$ とした場合、手順は
現在地 $x$ | $x$ の未探索な隣接点 | 探索木 $T$ に付加する辺 | キュー $Q$ |
| | | $\textcolor{white}{,}\textcolor{blue}{2}\textcolor{white}{,}$ |
$\textcolor{blue}{2}\textcolor{white}{,}$ | $0$, $3$, $4$ | $20$, $23$, $24$ | $\textcolor{blue}{0}$, $3$, $4$ |
$\textcolor{blue}{0}\textcolor{white}{,}$ | 無し | 無し | $\textcolor{blue}{3}$, $4$ |
$\textcolor{blue}{3}\textcolor{white}{,}$ | $1$ | $31$ | $4$, $1$ |
となり、幅優先探索木は
$T=$
となります。
Ex.13
二分木
$T=$
はそれ自体が全域木ですが、$v=0$ を根とする幅優先探索の手順は
現在地 $x$ | $x$ の未探索な隣接点 | 探索木に付加する辺 | キュー $Q$ |
| | | $\textcolor{white}{,}\textcolor{blue}{0}\textcolor{white}{,}$ |
$\textcolor{blue}{0}\textcolor{white}{,}$ | $1$, $2$ | $01$, $02$ | $\textcolor{blue}{1}$, $2$ |
$\textcolor{blue}{1}\textcolor{white}{,}$ | $3$, $4$ | $13$, $14$ | $\textcolor{blue}{2}$, $3$, $4$ |
$\textcolor{blue}{2}\textcolor{white}{,}$ | $5$, $6$ | $25$, $26$ | $3$, $4$, $5$, $6$ |
となります。すなわち頂点が探索される順番は
$$0,\ 1,\ 2,\ 3,\ 4,\ 5,\ 6$$
となります。
Rem.14(
ここ大事!)
幅優先探索の要点は
- 現在地 $x$(青い頂点) からは隣接点までしか見えない
- 未探索な隣接点のすべてへ枝を伸ばす
ことです。
※ 慣れてくれば、キューを横に書くだけで作業できるようになります。