BFS（幅優先探索）が最短路を見つけることは，アルゴリズムの教科書に当然のように書いてあります．しかし，なぜ幅優先に探索するだけで最短路が得られるのでしょうか？ DFS ではなぜダメなのでしょうか？ この記事では，「波紋」というアナロジーを使って，BFS の正当性の本質に迫ります．

1 波紋のアナロジー

静かな水面に石を落とすと，波紋が同心円状に広がっていきます．波紋はすべての方向に同じ速度で広がるので，ある地点に最初に到達した波は，必ず最短距離を通ってきたものです．

BFS はまさにこの波紋と同じことをしています．

始点$s$から「波紋」を広げると，次のように層が形成されます：

• 距離 0：$\{s\}$（始点自身）

• 距離 1：$\{A,B\}$（$s$ の隣接頂点）

• 距離 2：$\{C,D,E\}$（距離1の頂点の隣接頂点のうち未訪問のもの）

• 距離 3：$\{F\}$（距離2の頂点の隣接頂点のうち未訪問のもの）

BFS のキュー構造が，この「層ごとの展開」を正確に再現します．距離$k$の頂点をすべて処理し終えてから，距離$k+1$の頂点の処理に移ります．

2 BFS の正当性 ― なぜ波紋は嘘をつかないのか

BFS が最短路を正しく求めることの核心を述べます．

直感的な理由は次の通りです．

ポイントは，重みなしグラフでは各辺のコストが一定（すべて1）だということです．波の速度が一定だからこそ，最初に到達した波が最短なのです．

3 DFS が最短路を見つけない反例

DFS（深さ優先探索）は「一本道をとことん進んでから引き返す」探索です．これは波紋とは全く違う動きをします．

DFS の問題は，「深く潜る」ことを優先するため，近い頂点を飛ばして遠い頂点を先に訪問してしまうことです．波紋ではなく，迷路を壁伝いに歩くようなものです．

4 重み付きグラフ ― Dijkstra は「重みつきの波紋」

辺に重み（距離・コスト）がある場合，BFS の単純な波紋は通用しません．辺の重みが異なるので，「1ステップ = 1距離」という前提が崩れるためです．

ここで登場するのがDijkstra 法です．

なぜ非負重みが必要かも，波紋で理解できます．もし負の重みの辺があると，「すでに通り過ぎた場所に後から安いコストで到達できる」ことがあり得ます．波紋が逆流するようなもので，到達順序がコスト順序を保証しなくなるのです．

5 計算量の意味 ― なぜ$O(V+E)$なのか

BFS の計算量$O(|V|+|E|)$は，「各頂点を1回ずつ訪問し，各辺を1回ずつ調べる」ことを意味します．

Dijkstra 法の計算量$O((|V|+|E|)\log |V|)$（二分ヒープ使用時）は，BFS に比べて$\log |V|$倍のオーバーヘッドがあります．これはヒープ操作のコストで，「波紋の速度が辺ごとに異なる」ことの代償です．

6 まとめ

• BFS は「等速の波紋」です．辺の重みが均一だから，最初に到達 = 最短距離

• DFS は「壁伝い」なので最短路を保証しません

• Dijkstra は「可変速の波紋」で，非負重みの場合に最短路を求めます

• 負辺がある場合は波紋の比喩が破綻し，Bellman-Ford のような別のアプローチが必要になります

次の記事では，グラフの中でも特に美しい構造である「木」について考えます．