グラフ探索 — 波で塗るBFS、深く潜るDFS

迷路も、SNSの友達関係も、路線図も、すべて「点（節点）と、それをつなぐ線（枝）」＝グラフです。ある場所から行ける所をもれなく調べる2つの基本戦略 — 波のように広がるBFSと、行けるところまで潜るDFS — を、動かしながら体で覚えます。ちがいは「次にどこから調べるかを入れておく器」だけ。

1. 迷路はグラフ — マスが節点、隣どうしが枝

グラフとは、点（節点 / ノード）と、点をつなぐ線（枝 / エッジ）だけでできた抽象的な地図です。迷路なら、各マスが節点で、壁で仕切られていない隣のマスへの移動が枝にあたります。

探索とは「スタートから枝をたどって到達できるマスを、順序よく全部調べていく」こと。下の図では、スタート（S）から距離が等しいマスが同心円状の波になって広がります。まずはこの「つながり」の感覚をつかみましょう。

迷路をグラフとして見る — つながりの波

節点・枝を重ねて表示

白い点＝マス（節点）、細い線＝隣どうしの通行（枝）。水色の帯は、S から同じ歩数で行けるマスを波にしたものです。壁（濃い青）は通れません。この「点と線」の地図が、次からの探索の舞台になります。

POINT — 探索アルゴリズムの正体は「器の選択」どちらの探索も、やることは同じ手順の繰り返し：①フロンティア（次に調べる候補）から1つ取り出す → ②未訪問の隣を候補に加える。この「候補を入れておく器」がキュー（先入れ先出し）ならBFS、スタック（後入れ先出し）ならDFS。たったこれだけの違いで、探索の性格がまるで変わります。

2. 幅優先探索 BFS — 近い順に、波で塗る

BFS（Breadth-First Search / 幅優先探索）は、候補をキュー（FIFO：先に入れたものから取り出す）で管理します。すると探索は、スタートから距離1のマスを全部 → 距離2を全部 → … と、同心円状に外へ広がります。

この「近い順」という性質のおかげで、最初にゴールへ到達した経路が、そのまま最短（最少ステップ）になります。再生してキュー（下の帯）の中身の増減と、色の濃淡（距離の帯）を見比べてください。

BFS — 同心円の波でゴールを探す（キュー）

アニメ速度

明るい縁取り＝フロンティア（キューの中身＝次の波）。色の濃淡はスタートからの距離で、薄い水色ほど近く、紫ほど遠いので、探索が輪になって広がるのが見えます。ゴール到達で最短経路がオレンジに光ります。下の帯がキュー：左から取り出し、右へ追加（FIFO）。

BFS が最初に到達した距離＝最少ステップ数（重みなし最短経路）全ての枝のコストが等しいときだけ成り立つ。枝に重みが付くと崩れる → それを直すのが第9章のダイクストラ

注意 — BFS はメモリを食う BFS のフロンティア（キュー）は、波の円周ぶんのマスを同時に抱え込む。広い空間では円周が大きくなり、キューが一気に膨らむ。「最短が保証される」代わりに、DFS よりメモリを多く使いがち、という裏の顔がある。

3. 深さ優先探索 DFS — 行けるところまで潜る

DFS（Depth-First Search / 深さ優先探索）は、候補をスタック（LIFO：後に入れたものから取り出す）で管理します。すると探索は、一本道をどんどん奥へ奥へと潜り、行き止まりに当たって初めて一歩戻り（バックトラック）、別の枝へ進みます。

まるで細い蛇が穴を掘り進むよう（オレンジの帯がいま潜っている道＝スタックの中身）。全経路の列挙・連結成分の判定・トポロジカルソートなどで主役になりますが、最初に見つかる経路は最短とは限りません。同じ迷路でも、器を変えるだけで探索順がまるで違うことを確かめましょう。

DFS — 一本道を奥まで掘り進む（スタック）

アニメ速度

オレンジの太い線＝いま潜っている道（スタックにS〜現在地が積まれた状態）。行き止まりに当たると一歩戻って別の枝へ。色は発見の新しさ（緑→桃）。BFS の同心円とは対照的に、探索が一方向へ細長く伸びるのが DFS の個性です。

POINT — 同じ迷路・同じ隣接規則、なのに別物 BFS と DFS は、隣を調べる順番も、通れる枝も全く同じ。違うのは候補を取り出す順（キュー/スタック）だけ。それだけで、探索は「広く浅く（波）」にも「狭く深く（蛇）」にもなる。データ構造の選択がアルゴリズムの性格を決める好例です。

4. BFS vs DFS — 並べて体感、そしてまとめ

最後に、同じ迷路で BFS と DFS を同時に走らせて見比べます。同じスタート・同じゴールでも、たどり着くまでに調べるマスの順番も、見つかる経路の長さも違います。BFS の経路は必ず最短、DFS の経路は運任せ、という差に注目してください。

せーので比較 — 左BFS（波）／右DFS（蛇）

アニメ速度

両者とも1手ずつ同時に進みます。BFS（左）は同心円で着実に、DFS（右）は寄り道しながら。到達後は経路長を表示：BFS は最短、DFS はしばしば遠回り。ただし調べたマスの総数（探索コスト）はケースによってどちらが少ないか変わります。

時間計算量＝ O(V + E)　　（V＝節点数、E＝枝数） BFS も DFS も、各節点と各枝を一度ずつ見るだけ。迷路が N マスなら、ほぼ N に比例した手間で全域を調べ切れる

BFS（キュー・FIFO）：近い順に波で広がる。重みなしなら最短経路を保証。ただしフロンティアが太くメモリを食いやすい。
DFS（スタック・LIFO）：行けるところまで潜り、行き止まりで戻る。メモリは道の深さぶんで済むが、最短は保証しない。全列挙・連結判定・トポロジカルソート向き。
両者の違いは「候補を入れる器」だけ。手順（取り出す→隣を足す）は共通で、計算量はどちらも O(V+E)。

一歩先へ — 枝に「重み」がつくと世界が変わるここまでは全ての移動が「1歩」で等しかった。でも現実の地図は、道ごとに距離も混雑も違う＝枝に重み（コスト）がある。すると「歩数が少ない＝速い」が崩れ、BFS では最短が測れない。距離ラベルを賢く伸ばすダイクストラ法、ゴールへ当たりをつけて掘るA* が主役になる — それが第9章「最短経路」です。