BFS（幅優先探索）アルゴリズムをわかりやすく解説

幅優先探索、つまり BFS は、開始ノードからの距離の順にノードを訪れるグラフアルゴリズムです。まず 1 本の辺で到達できるノードをすべて調べ、その後に 2 本の辺、3 本の辺で到達できるノードへと進みます。

この階層ごとの順序が重要な考え方です。グラフが 重みなし、またはすべての辺のコストが同じなら、BFS は開始ノードから到達可能な各ノードまでの最短経路長も求められます。

幅優先探索がすること

BFS は キュー を使います。キューは先入れ先出しのリストです。キューがあることで階層順が保たれ、先に見つかったノードほど先に処理されます。

基本的な流れは次のとおりです。

各ノードの親も記録しておけば、探索が終わったあとで最短経路の 1 つを復元できます。

ノード $A$ を開始点だとします。 $A$ に直接つながる隣接ノードは $A$ からの距離が $1$ なので、最初にキューへ入ります。それらのノードを処理し終えてから、その未訪問の隣接ノードが入るため、次の波は距離 $2$ になります。

このため、BFS は開始点からの距離ごとにノードを自然にグループ分けします。どの経路が短そうかを推測しているわけではありません。キューによって、より長い経路を考える前に、辺の本数が少ないすべての経路を先に処理することになります。

次のグラフを使います。

A \to \{B, C\}, \qquad B \to \{D\}, \qquad C \to \{E\}, \qquad D \to \{F\}, \qquad E \to \{F\}

$A$ から始めると、キューは次のように変化します。

[A] \to [B, C] \to [C, D] \to [D, E] \to [E, F] \to [F]

これは次の意味です。

まず $A$ を処理し、そのあとに $B$ と $C$ を追加します。次に $B$ 、その次に $C$ を処理すると、 $D$ と $E$ が追加されます。その後で $D$ と $E$ を処理すると、 $F$ に到達します。

したがって、BFS の訪問順は次のようになります。

A,\ B,\ C,\ D,\ E,\ F

$A$ からの距離は次のとおりです。

\operatorname{dist}(A)=0,\quad \operatorname{dist}(B)=1,\quad \operatorname{dist}(C)=1,\quad \operatorname{dist}(D)=2,\quad \operatorname{dist}(E)=2,\quad \operatorname{dist}(F)=3

ここに BFS の大きな利点があります。BFS は距離 $3$ で $F$ に到達するので、 $A$ から $F$ への最短経路は 3 本の辺を使います。最短経路の 1 つは $A \to B \to D \to F$ です。もう 1 つは $A \to C \to E \to F$ です。

それが成り立つのは、すべての辺のコストが同じ場合、またはグラフを重みなしとして扱う場合だけです。辺の重みが異なると、BFS は辺の本数は少ないが合計コストは高い経路を見つけることがあります。

標準的な BFS では、ノードはあとで取り出すときではなく、キューに入れる時点 で訪問済みにするのが普通です。そうすることで、同じノードが何度もキューに追加されるのを防げます。

BFS は階層ごとに探索します。一方、深さ優先探索である DFS は、いったん 1 本の枝をできるだけ深くたどってから戻ります。どちらも得意な問題の種類が異なります。

同じ階層の中での正確な訪問順は、隣接ノードがどの順で並んでいるかによって変わることがあります。距離に関する保証はそのままですが、たどる順序は異なる場合があります。

BFS は、到達可能性を調べたいとき、木におけるレベル順走査、または辺の本数で測る最短経路長を求めたいときに役立ちます。

また、各操作のコストが同じ状態空間問題にもよく現れます。この条件では、最小の手数を求める方法として BFS が最もわかりやすいことがよくあります。

BFS は、開始ノードから外側へ波紋が広がっていく様子だと考えるとわかりやすいです。波紋が 1 回広がるごとに、距離が辺 1 本分だけ増えます。

自分で試すなら、小さなグラフを描いて開始ノードを 1 つ選び、各ステップのあとでキューの中身を書き出してみましょう。次の練習としては、似たグラフ探索の問題を解き、グラフに重みがある場合でも最短経路の主張が成り立つかを確かめてみてください。

問題をアップロードすると、検証済みのステップバイステップ解答が数秒で届きます。