BFS vs DFS ビジュアライザー

BFSとDFSが同じグラフをどのように違って探索するかを見てみましょう。BFSは広く、DFSは深く進みます。

初期値 — BFS vs DFS ビジュアライザー

グラフのプリセット	4×4グリッド
開始ノード	0

上のコントロールを変えると、ここから結果が計算し直されます。

インタラクティブシミュレーションを読み込んでいます...

BFS が最短経路を保証するのは、すべての辺のコストが等しいときだけ 🖖

BFS を選ぶ通常の理由は、最短経路を返してくれることです。しかしこの保証は聞こえよりも狭いものです。BFS はすべての辺を 1 歩として扱うため、あるノードに初めて到達したときには必然的に最小の跳躍数で来ていることになり、そこから保証が生まれています。現実のコスト、たとえば道路の距離、乗り換え料金、遅延を持ち込むと、この保証は消えます。BFS はそれでも自信をもって答え、そして間違えます。高価な辺を 2 本たどる経路が、安い辺を 5 本たどる経路より高くつくことは容易に起こるからです。ダイクストラ法がその修正であり、その中身はほぼこれだけです。BFS の素のキューを優先度付きキューに置き換えるのです。

同じ地図、異なる旅のしかた 🖖

両者を並べて動かすと気づくことがあります。訪れるノードと辺はまったく同じで、違うのは順序だけです。幅優先探索(BFS)は先へ進む前に現在の近傍をすべて調べるため、境界で待っているすべてのノードを覚えておく必要があります。深さ優先探索(DFS)は一つの枝に踏み込み、いま辿っている経路だけを追います。実用的な結論は、答えが近くにありそうなら BFS、グラフが深くメモリを小さく保ちたいなら DFS を選ぶことです。

どちらの探索も迷路から生まれた 🖖

コンピュータのはるか以前、DFS はフランスの数学者シャルル・ピエール・トレモー(Charles Pierre Trémaux)が1800年代に発表した迷路の歩き方の規則として存在していました。BFS の登場はずっと後で、Edward F. Moore が1959年に The Shortest Path Through a Maze という題名そのままの論文で再発見し、Konrad Zuse も1945年にすでに素描していました。計算機科学の二本の柱は、どちらも元は迷路を抜け出すために考案されたのです。

グラフ探索 — どの順序が必要で、その代償は何か

あなたはどの探索のケースにいますか？

BFS と DFS は同じ頂点を訪ね、違うのはコード 1 行だけです。スタックの代わりにキューを使う。あとはすべてそこから決まります。キューは輪を描いて外へ広がるので、BFS がある頂点に初めて着いたとき、その道は辺の数が最小です。スタックは潜るので、DFS のほうが遠い端に早く着きますが、道筋は特に決まっていません。どちらが要るかは問いによって決まり、そして各々の代償はグラフの形が決めます。

辺の数を最小にしたい — 距離の層ごとに訪ねる BFS FIFO ⇒ min |E|

木の場合 — 幅の順と行きがけ順、そして記憶の負担が入れ替わる BFS: O(w), DFS: O(d)

鎖の場合 — 二つの順序が一致し、選択の意味がなくなる deg ≤ 2 ⇒ BFS = DFS

すべてに手が届くわけではない — 出発点 1 つでは足りない c(G) > 1

辺の数を最小にしたい — 距離の層ごとに訪ねる BFS

わかっていること: 重みのないグラフと最短路の問い。BFS は距離 1 のものをすべて、次に距離 2 のものをすべて訪ねるので、ある頂点への最初の到着は最短路を通っています。

規則: FIFO ⇒ min |E|

計算例: 4×4 の格子で頂点 0 から始めると、BFS は 0, 1, 4, 2, 5, 8, 3, 6, 9, 12, … と斜めの波面で進みます。DFS は 0, 1, 2, 3, 7, 6, 5, 4, … と進み、頂点 4 に着くのは 8 歩目です。

このケースを開く: 4×4グリッド

辺の数を最小にしたい — 距離の層ごとに訪ねる BFS. BFS は距離の層ごとに外へ掃き、DFS はまず一本の通路を蛇行して下ります。重みのないグラフと最短路の問い。BFS は距離 1 のものをすべて、次に距離 2 のものをすべて訪ねるので、ある頂点への最初の到着は最短路を通っています。 — BFS は距離の層ごとに外へ掃き、DFS はまず一本の通路を蛇行して下ります。

木の場合 — 幅の順と行きがけ順、そして記憶の負担が入れ替わる

わかっていること: 木では二つの順序に名前があります。BFS は幅の順、DFS は行きがけ順です。どちらも 15 頂点すべてを訪ねます。違うのは同時に抱えておく量です。

規則: BFS: O(w), DFS: O(d)

計算例: BFS は 0, 1, 2, 3, …, 14 と階層ごとに進みます。DFS は 0, 1, 3, 7, 8, 4, 9, 10, 2, … と、まず左の背骨を下ります。キューの最大は 8、スタックの最大は 4。

このケースを開く: 二分木

木の場合 — 幅の順と行きがけ順、そして記憶の負担が入れ替わる. 幅の順は各段を埋めてから下り、行きがけ順は葉まで走ってから戻ります。木では二つの順序に名前があります。BFS は幅の順、DFS は行きがけ順です。どちらも 15 頂点すべてを訪ねます。違うのは同時に抱えておく量です。 — 幅の順は各段を埋めてから下り、行きがけ順は葉まで走ってから戻ります。

鎖の場合 — 二つの順序が一致し、選択の意味がなくなる

わかっていること: どの頂点にも未訪問の隣がちょうど 1 つしかないので、進む道は一本きりです。BFS と DFS は同じ並びを生み、一度に 1 頂点しか抱えません。

規則: deg ≤ 2 ⇒ BFS = DFS

計算例: 12 頂点の鎖ではどちらも 0, 1, 2, …, 11 の順に訪ね、前線は最初から最後まで大きさ 1 のままです。

このケースを開く: 長いチェーン

鎖の場合 — 二つの順序が一致し、選択の意味がなくなる. 分岐する先がなければ、どちらの探索も同じ線を同じ順に歩きます。どの頂点にも未訪問の隣がちょうど 1 つしかないので、進む道は一本きりです。BFS と DFS は同じ並びを生み、一度に 1 頂点しか抱えません。 — 分岐する先がなければ、どちらの探索も同じ線を同じ順に歩きます。

すべてに手が届くわけではない — 出発点 1 つでは足りない

わかっていること: グラフが分かれています。ある頂点から始めると、どちらの探索もその頂点の属する連結成分だけを訪ね、そこで止まります。

規則: c(G) > 1

計算例: 10 頂点のグラフの頂点 0 から始めると、BFS も DFS もちょうど 4 頂点を訪ねて止まります。頂点 4, 5, 6, 7, 8, 9 には一度も触れません。

このケースを開く: 非連結

すべてに手が届くわけではない — 出発点 1 つでは足りない. 到達できる頂点は 4 つ、できない頂点は 6 つ。出発点 1 つは成分 1 つしか調べません。グラフが分かれています。ある頂点から始めると、どちらの探索もその頂点の属する連結成分だけを訪ね、そこで止まります。 — 到達できる頂点は 4 つ、できない頂点は 6 つ。出発点 1 つは成分 1 つしか調べません。

参考文献 (2)

Insight block 3 — BFS as a maze algorithm: E. F. Moore, "The shortest path through a maze." Proceedings of an International Symposium on the Theory of Switching, Part II, 285–292. Harvard University Press, 1959.
Trémaux's rule, as it was actually published: É. Lucas, Récréations mathématiques, vol. 1. Gauthier-Villars, Paris, 1882 — Lucas credits the maze-walking procedure to Charles Pierre Trémaux.

全プロセスの詳細解説

16 ノードと 16 エッジを持つ迷路の探索 5 ステップ
迷路には16個のノードがあり、16本のエッジで接続されている。ノード 0 から開始する探索が到達するノード数と、ノード 15 がノード 0 からどれだけ離れているかを求めよ。これは開始ノード 0 における迷路の通路状態である。
1. 何よりも先に、迷路を隣接リストとして書き出す。注目すべきはノード 4 である。1本のエッジも接触していないため、その次数は 0 であり、他のどこから開始する探索もここに到達することはない。
  
  $0 : 11 : 0, 2, 52 : 1, 33 : 24 : \emptyset 5 : 1, 6, 96 : 5, 7, 107 : 6, 118 : 9, 12 9 : 5, 8, 1010 : 6, 9, 1411 : 7, 15 12 : 8, 1313 : 12, 1414 : 10, 1315 : 11$
2. 幅優先探索は、到達可能なノードを階層（レイヤー）に分類する。レイヤー k は、レイヤー k − 1 から初めて到達したすべてのノードで構成される。それらの構築は周回（ウォーク）というよりは閉包プロセスである。次のレイヤーを開く前に現在のレイヤーを完全に終了し、どのノードも2度現れることはない。
  
  $L_{0} L_{3} L_{6} = {0} = {3, 6, 9} = {13, 15} L_{1} L_{4} = {1} = {7, 8, 10} L_{2} L_{5} = {2, 5} = {11, 12, 14}$
3. 各レイヤーのサイズを加算する。探索は15個のノードに到達するが、これはグラフに含まれる16個より1つ少なく、ステップカウンターがノード数より1少ない値で停止するのはそのためである。
  
  $1 + 1 + 2 + 3 + 3 + 3 + 2 = 15, n = 16, de g (4) = 0$
4. ノード 15 はレイヤー 6 に初めて現れ、レイヤー番号は距離を表す。ノードは1つ上のレイヤーのノードからのみキューに追加されるため、レイヤー 6 のノードに6本未満のエッジで到達することはできない。経路 0-1-5-6-7-11-15 は 6 を達成するため、この下限は厳密である。
  
  $15 \in L_{6} ⟹ d (0, 15) = 6 : 0 \to 1 \to 5 \to 6 \to 7 \to 11 \to 15$
5. 深さ優先探索には、そのような不変条件はない。頂点1で2より先に5へ、頂点5で6より先に9へ、頂点9で10より先に8へ進むとしよう。いずれも未訪問の隣接頂点から選ぶ正当な手だが、これによって探索は長い経路へ入り込み、進める頂点がなくなるまで後戻りしない。その果てで、12本の辺からなる経路の終点として頂点15に到達する。この経路も、到達可能性を問う問題へのまったく正しい答えである。
  
  $0 \to 1 \to 5 \to 9 \to 8 \to 12 \to 13 \to 14 \to 10 \to 6 \to 7 \to 11 \to 15 ⟹ ℓ = 12$
解答

ノード 15 は開始位置から6本のエッジの距離にあり、深さ優先探索を行うと同じ場所への経路として12を返す可能性がある。 2倍という倍率は本質的な部分ではない。興味深いのは、どこから近道が生じ得るかである。到達可能な連結成分は15個のノードを持つため、その任意の全域木は14本のエッジを使用する。そして迷路には16本のエッジがあるため、ちょうど2本のエッジが余剰となる。それら2本を削除すると残りは木となり、任意のノード対の間に存在する経路はただ1つとなる。そのため、2つのパネルはすべての距離について一致し、探索する順序のみが異なることになる。距離に関する両者のすべての相違は、これら2本の余分なエッジに起因している。これこそが、単にノードに到達可能かどうかだけを問う場合には深さ優先探索のコストが低く、距離がどれくらいかを問う問題になった瞬間には不適切な選択となる理由である。

$∣ E ∣ - (∣ V ∣ - 1) = 16 - (15 - 1) = 2$

42Math チーム · 更新 2026-07-27

公表された資料と照合しています。訂正のご指摘を歓迎します。編集方針 · 訂正

コンピューティングのレッスン一覧 →

例題

4×4グリッド - 4×4グリッド: BFSは層ごとに探索する
迷路の通路 - 迷路の通路
スターグラフ - 九本のスポーク。どのノードも中心から一ホップの距離です。奥へ進める場所がないため、深さ優先探索も幅優先探索と同じ順序を返します。
長いチェーン - 一直線に並んだ十二のノード。ここでも順序は一致します。ただ星型のときの九つとは異なり、ここでは各アルゴリズムが一度に保持するノードは一つだけです。
二分木 - 二分木: DFSは幅よりも深さを優先して進む
非連結 - 二つの四角形と、二つの孤立したノード。ノード0からの探索では10個のうち4個に到達しますが、残りはいくら探しても見つかりません。
密なグラフ - 密なグラフ: 辺が多く、探索順序が似通う