幅優先探索

幅優先探索（BFS）は、始点からの距離が近い順にノードを訪問します。発見済みで処理待ちのノードを、先入れ先出しのキューで管理します。重みのないグラフでは、最初の到達で辺数が最小の経路を求められます。時間計算量は O(V + E) です。

水面の波紋は近くから遠くへ広がります。BFS のキューも同じ層順序を保ちます。新しいノードは末尾に入り、次に処理するノードは先頭から出ます。後で見つかった次の層が、前で待つノードを追い越しません。

幅優先探索の仕組み

始点をキューに入れ、訪問済みとし、距離を 0 にします。キューが空でない間、先頭のノードを取り出して隣接ノードを調べます。未発見の隣接ノードには現在の距離に 1 を加えた値を記録し、訪問済みにして末尾へ入れます。

訪問済みの印は、キューへ入れる時点で付けます。 取り出すまで印を付けず、別の重複対策もなければ、複数の隣接ノードから同じノードを何度も追加する場合があります。後の経路で距離を上書きする原因にもなります。グラフモードのコードでは、visited.add(nb) と追加処理を同じ if nb not in visited 分岐に置きます。

このレッスンには二つのモードがあります。Tree モードでは、根から各ノードへの経路が一つで、経路の合流がありません。コードは訪問済み集合を省略します。Graph モードでは合流や閉路があるため、集合で重複発見を防ぎます。発見済みノードへの辺は再追加せずにスキップします。行き先が BFS 木で現在のノードの祖先なら back edge、それ以外なら cross edge と表示します。

ノードは距離が減らない順にキューから出ます。初めてノードを発見する経路より、後の経路が短くなることはありません。したがって、その時点で重みのないグラフの最短距離が確定します。

幅優先探索のステップ

初期設定は Graph モード、Simple プリセット、始点 0 です。七つのノードがあり、接続は 0 → [1, 2]、1 → [3, 4]、2 → [5]、4 → [5]、5 → [6] です。3 と 6 に後続ノードはありません。5 へは 2 と 4 の両方から到達できます。

1. 0 を追加：訪問済みにし、距離は d = 0、キューは [0] です。
2. 0 を取り出す：1 と 2 を発見し、どちらも d = 1 にします。キューは [1, 2] です。
3. 1 を取り出す：3 と 4 を発見し、どちらも d = 2 にします。キューは [2, 3, 4] です。
4. 2 を取り出す：5 を初めて発見します。親を 2、距離を d(5) = 2 とし、キューは [3, 4, 5] になります。
5. 3 を取り出す：新しいノードはなく、キューは [4, 5] です。
6. 4 を取り出す：4 → 5 の到達先 5 は発見済みです。この経路は三辺で、既存の二辺の経路より短くありません。追加せず、キューは [5] です。
7. 5 を取り出す：6 を発見し、d = 3 にします。キューは [6] です。続いて 6 を取り出すと、新しいノードはなく、キューが空になります。

訪問順は 0、1、2、3、4、5、6、層ごとの距離は 0 / 1、1 / 2、2、2 / 3 です。六番目の処理では、訪問済み集合が 5 への二度目の到達をスキップに変えます。

Tree モードの Balanced プリセットでは、完全二分木を 0, 1, 2, 3, 4, 5, 6 の層順で訪問し、合流はありません。同じ木を DFS の先行順で訪問すると 0, 1, 3, 4, 2, 5, 6 です。グラフの Cyclic プリセットでは、閉路を閉じる辺が発見済みノードを指すため、スキップされます。

画面下部のキューでは、要素が末尾から入り、先頭から出ます。ノードは未到達なら薄い青、発見済みで処理待ちならオレンジ、走査済みなら緑です。d= が距離を示し、スキップする辺（back / cross）は赤く点滅します。

時間・空間計算量

到達可能な各ノードは、キューへ一回入り、一回出ます。訪れた隣接リストの各項目も一回ずつ調べます。キューと訪問済み集合が使う領域は最大 O(V) です。

幅の広い層はキューを大きくします。一つの層を処理する途中では、その層の残りと、次の層の発見済みノードがキューに共存することもあります。長い鎖では通常、キューは短く保たれます。DFS は深い経路で領域を使いますが、どちらも最悪追加領域は O(V) です。

境界条件

• 一ノード・辺なし：始点を追加して取り出すと、隣接先がないため終了します。
• 非連結グラフ：始点から到達可能なノードだけを訪れます。無向グラフでは始点の連結成分です。全体を訪れるには、未訪問のノードから探索を再開します。
• 閉路：発見済みの印が再追加を防ぐため、キューが無限に増えません。
• 幅と深さ：広い探索境界は大きなキューを使います。長い鎖では通常、小さなキューで済みます。

よくある間違い

1. 取り出す時点で印を付け、重複を防がない：複数の隣接先から同じノードが追加されます。この実装では、追加時に印を付けます。
2. 異なる辺重みの最短路にも通常の BFS を使う：BFS が最小化するのは辺数です。総コストの最小化になるのは辺のコストが等しい場合です。非負重みには Dijkstra 法を使えます。
3. キューをスタックに変える：先入れ先出しが後入れ先出しになり、層順ではなく経路を深く進む順序になります。ライブラリの pop がどちら側を取り出すか確認します。
4. グラフモードで訪問済み集合を省く：閉路が同じノードを繰り返し追加します。経路の合流や閉路がない木構造でのみ、この重複防止を省けます。