BFS と DFS アルゴリズムとは？それぞれを選ぶべき場面
BFS と DFS は、開始頂点から到達可能な頂点を体系的に見つけるグラフ探索アルゴリズムです。BFS は近い頂点からレベルごとに探索範囲を広げるため、重みなしグラフで辺の本数が最小の経路が必要な場合に適しています。DFS はバックトラックする前に 1 つの枝を可能な限り深くたどるため、構造解析、閉路検出、トポロジカルソートなどの問題の基礎として使われます。どちらかが常に優れているわけではなく、経路の基準とグラフの目的によって選択します。 ocw.mit.edualgs4.cs.princeton.edu
BFS と DFS はグラフ探索で何を見つけるのか？
グラフは、頂点と辺からなる関係構造です。頂点は人、都市、Web ページ、タスクなどの実体を表し、辺は友人関係、道路、リンク、前提条件の関係など、それらの接続を表します。頂点の集合を 、辺の集合を で表します。
辺に方向がないグラフは無向グラフです。たとえば、相互の友人関係は通常、双方向と見なせます。これに対して、A が B をフォローする関係や、タスク A を完了してからタスク B に進む必要がある関係は、有向グラフを形成します。有向グラフでは矢印の向きにしか進めず、逆方向へ自動的に移動することはできません。 ocw.mit.edu
グラフ探索における最も基本的な問いは、「開始点 から到達できる頂点はどれか」です。この問いに答える過程で、BFS と DFS は、頂点が訪問済みかどうか、各頂点に最初に到達した経路、探索順序などの追加情報も記録できます。ただし、1 つの頂点から開始する探索が処理するのは、その頂点から実際に到達可能な部分だけです。グラフ内のすべての頂点を必ず訪問するとは限りません。 ocw.mit.edu
木もグラフの一種です。そのため、BFS と DFS は、フォルダ階層や組織図など、木に見える問題にも利用できます。ただし、一般のグラフには、頂点へ戻る閉路や同じ頂点への複数の経路が含まれる可能性がある点を覚えておくことが重要です。木の走査だけを想定した実装を一般のグラフにそのまま適用すると、重複訪問が発生することがあります。
BFS はどのように近い頂点から探索するのか？
BFS は Breadth-First Search（幅優先探索）の略です。まず開始点から 1 本の辺で到達できる頂点を見つけ、次に 2 本の辺が必要な頂点、さらに 3 本の辺が必要な頂点という順に、探索範囲を広げます。ここでいう距離は物理的な距離やコストではなく、開始点からたどる必要がある辺の本数です。 algs4.cs.princeton.edu
BFS は通常、このためにキューを使用します。キューは FIFO（First In, First Out）型のデータ構造で、最初に追加した要素が最初に取り出されます。開始頂点をキューに入れて訪問済みとしてマークし、キューの先頭から頂点を 1 つ取り出します。その頂点の未発見の隣接頂点をすべて訪問済みとしてマークし、キューの末尾に追加します。キューが空になるまでこれを繰り返します。先に発見された近い頂点が先に処理されるため、レベルごとの拡張が維持されます。 gh.cp-algorithms.comalgs4.cs.princeton.edu
たとえば、A から開始して A の隣接頂点 B と C を発見したとします。BFS が B を処理すると B の隣接頂点を発見し、次に C を処理して C の隣接頂点を発見します。B から発見された頂点がより深い階層にあっても、同じレベルですでにキューに入れられた C は、先に、または近接した順番で処理されます。B と C の正確な順序は、隣接頂点の格納順序によって異なります。
BFS の重要な点は、頂点を発見した時点ですぐに訪問済みとしてマークすることです。キューから取り出すまでマークを遅らせると、2 つの頂点がそれぞれ同じ隣接頂点を発見し、その頂点を複数回キューに入れてしまうことがあります。一般的な BFS では、新しい隣接頂点をキューに追加するまさにその時点で発見済みとしてマークするほうが、単純かつ安全です。
BFS が最短経路を提供するのはどのような条件か？
BFS がよく選ばれる理由は、重みなしグラフにおいて、開始頂点から到達可能なすべての頂点への辺の本数が最小の経路を見つけるためです。開始点から 1 ステップ離れたすべての頂点を、2 ステップ離れた頂点より先に調べるため、ある頂点を最初に発見した経路より少ない辺で構成される経路が後から現れることはありません。BFS 中に各頂点を最初に発見したとき、直前の頂点を親として記録すれば、それらの親ポインタは最短経路木を形成します。 algs4.cs.princeton.edu
経路を復元するには、対象頂点から開始頂点まで親ポインタを逆向きにたどり、その順序を反転します。たとえば、parent[D] = B および parent[B] = A であれば、A から D への発見された経路は A → B → D です。開始頂点には親がいないことを示すため、別のマーカーを使います。
ただし、「最短」を広く解釈しすぎると誤りにつながります。BFS が保証するのは、すべての辺を同じコストとして扱える場合に限った、辺の本数の最小値です。道路の所要時間が異なったり、航空券の運賃が異なったりする場合、2 本の辺を使う経路のほうが、1 本の辺だけを使う経路より安価または高速なことがあります。その場合、標準的な BFS はコストに関する最短経路アルゴリズムではありません。重みの性質に応じて、ダイクストラ法やベルマン・フォード法など、専用の重み付き手法を検討してください。 algs4.cs.princeton.edu
したがって、BFS は「2 人の友人は何人のつながりで隔てられているか」や、「上下左右に 1 マス移動することを 1 回と数えるグリッドで、ある地点に到達するには何回の移動が必要か」といった問題に適しています。対して、最短時間や最低コストが目的であれば、まず辺の重みが本当に等しいかを確認してください。
DFS はなぜバックトラックする前に深く進むのか？
DFS は Depth-First Search（深さ優先探索）の略です。現在の頂点から未訪問の隣接頂点を 1 つ選び、可能な限り深く枝を探索するまで進み続けます。行き止まりに達すると、直前の頂点へ戻り、まだ探索していない別の隣接頂点を探します。この戻る処理はバックトラックとも呼ばれます。 ocw.mit.edu
DFS は再帰呼び出しで簡単に実装できます。頂点に入ったら、まず訪問済みとしてマークし、その頂点の未訪問の隣接頂点ごとに同じ探索関数を呼び出します。再帰呼び出しが終了すると、制御は自然に呼び出し元へ戻るため、深く進んでからバックトラックする流れを表現できます。
再帰だけが選択肢ではありません。DFS は明示的なスタックを使って反復的に実装することもできます。スタックは LIFO（Last In, First Out）型のデータ構造で、最後に追加した要素が最初に取り出されます。最も最近発見した頂点を先に取り出すことで、深さ優先の動作を実現できます。再帰実装では、プログラムの呼び出しスタックが暗黙的にこの役割を担います。 ocw.mit.edugh.cp-algorithms.com
DFS によって作成される親ポインタも、開始頂点からある頂点までの 1 つの経路を示せます。ただし、その経路が辺の本数において最小である保証はありません。DFS は最初に選んだ枝を可能な限り深くたどるため、別の枝にあるより短い経路を後になって初めて発見する場合があります。 ocw.mit.edu
どのような構造解析で DFS を使うのか？
DFS は、単に到達可能性を確認するのではなく、グラフの構造を解析する際に価値を発揮します。連結成分の発見は代表例です。無向グラフでは、未訪問の任意の頂点から DFS を 1 回実行すると、その頂点に連結しているすべての頂点を 1 つのグループとして見つけられます。残っている未訪問の頂点から再び DFS を開始すれば、別のグループを見つけられます。
閉路検出も DFS の一般的な用途です。閉路とは、辺をたどることで開始頂点、または現在の経路上にすでにある頂点へ戻ることができる構造です。有向グラフでは、現在の再帰経路上にすでに存在する頂点に遭遇したかどうかを区別することで、閉路を検出できます。そのため、単に一度訪問された頂点と、現在探索中の経路上にある頂点を区別する必要があります。
トポロジカルソートは、タスク間の前提条件のような有向依存関係を順序として並べます。これは、有向非巡回グラフ、すなわち DAG でのみ可能です。DAG とは、辺の向きに従って進んでも開始点に戻る閉路がない有向グラフです。閉路が存在すると、たとえば B は A より前に完了しなければならず、同時に A は B より前に完了しなければならないという矛盾が生じるため、すべての辺を満たす線形順序は存在しません。DFS の終了順序を用いる手法は、トポロジカルソートの基礎の 1 つです。 algs4.cs.princeton.edu
強連結成分の発見も、DFS に基づく重要なテーマです。強連結成分とは、有向グラフにおいて同じグループ内の任意の 2 頂点が互いに到達可能な頂点集合です。ただし、この問題は単純な DFS を 1 回実行するだけでは解けず、探索順序と辺の向きを利用するアルゴリズム的な構成が必要です。 algs4.cs.princeton.edu
訪問済みマーカーがないとどのような問題が起こるのか？
一般のグラフでは、訪問済み配列または集合は任意のものではなく、終了性と正確性のために不可欠です。たとえば、A と B が接続されている場合、A から B に進み、B から A に戻れます。訪問済み状態を確認しなければ、DFS は A と B の間を永遠に再帰的に往復する可能性があり、BFS は同じ頂点をキューに複数回入れる可能性があります。 ocw.mit.edu
visited という概念は、実装によってやや異なる形に分けられます。BFS では通常、頂点をキューに追加した瞬間に「発見済み」としてマークします。DFS では、頂点の関数に入った直後に訪問済みとしてマークするのが一般的です。より高度な有向グラフ解析では、未訪問、現在探索中、完了済みの状態を区別することがあります。
各頂点を 1 回だけ訪問するという原則は、探索の効率に直結します。すでに処理した頂点を展開しなければ、隣接リストでは各頂点と各辺を限られた回数だけ調べることになります。また、頂点を最初に発見したときだけ親ポインタを設定すれば、その頂点を最初に発見した経路が明確になります。
グラフ全体を走査するには、外側のループが必要です。すべての頂点を順に調べ、まだ訪問されていない頂点を見つけるたびに、そこから新しい BFS または DFS を開始します。無向グラフでは、これにより連結成分ごとの探索が行われます。有向グラフでは、選択した辺の向きにおいて到達可能な範囲を順次処理します。 ocw.mit.edu
時間計算量がグラフ表現に依存するのはなぜか？
BFS と DFS の時間計算量は、しばしば とされます。これは隣接リストを使用する場合の標準的な解析です。隣接リストは、各頂点について直接接続されている隣接頂点のリストを格納します。訪問済みマーカーを使う場合、各頂点は 1 回処理され、辺は隣接リストを走査する際に確認されるため、総作業量は頂点数と辺数の和に比例します。 ocw.mit.edu
追加の空間は通常 です。これには、訪問済み配列、親配列、BFS のキューまたは DFS のスタックが含まれます。再帰 DFS では、再帰の深さに必要な呼び出しスタックも追加空間に含まれます。グラフ自体を格納する空間と、探索アルゴリズムが使用する追加空間を区別すると便利です。 ocw.mit.edu
隣接行列は、頂点の各組に対する辺の存在を表形式で格納します。ある頂点の隣接頂点を見つけるには、可能なすべての頂点を調べる必要がある場合があります。そのため、隣接行列を使用する BFS や DFS は通常、 の時間を要することがあります。辺が少ない疎グラフでは、実際に接続されている隣接頂点だけを走査する隣接リストが特に効率的です。 ocw.mit.edu
| 表現 | 隣接頂点の確認方法 | 代表的な探索時間 |
|---|---|---|
| 隣接リスト | 実際に接続されている隣接頂点のリストを反復処理する | |
| 隣接行列 | 可能なすべての頂点との接続を確認する |
計算量の記法は、入力サイズが増加したときにリソース使用量がどのように増える傾向にあるかを表します。実際の実行時間は、頂点識別子、隣接リストの実装、メモリレイアウト、探索の開始点から到達可能な部分の大きさにも影響されます。それでも、アルゴリズムを選ぶ際には、まずグラフが疎かどうか、どのように表現されているかを確認するのが妥当です。
BFS または DFS の実際の訪問順序は固定されているのか？
いいえ。BFS は近いレベルを先に処理する原則に従い、DFS は現在の枝を深く探索する原則に従いますが、同じレベル内でどの頂点を先に訪問するか、複数の隣接頂点のうちどの枝を先に探索するかは、隣接頂点の格納順序に依存します。 gh.cp-algorithms.comgh.cp-algorithms.com
たとえば、A の隣接リストが B、C の順なら、BFS は一般に B を先に発見します。リストを C、B の順に変更すると、C が先に発見される場合があります。この違いは DFS ではより大きな影響を与えます。最初に選ばれる隣接頂点が変わると、深く探索される枝自体が変わり、親ポインタによって作られる探索木や DFS の経路も変わります。
この事実は、アルゴリズムの結果を評価する際に重要です。問題が「辞書順で最初の訪問順序」を要求する場合は、隣接リストをソートするか、優先規則を指定する必要があります。対して、到達可能性、連結成分の数、または辺数が最小の距離だけが必要な場合、同じレベルや深さにおける詳細な順序は結果の中心ではないことがあります。
特に、スタックを使って DFS を反復実装する場合、隣接頂点をプッシュする順序は、実際に取り出される順序とは逆になることがあります。指定された隣接リスト順序を使う再帰実装と同じ訪問順序にしたい場合は、隣接頂点をスタックへプッシュする方向を意図的に調整する必要があります。これは DFS の定義が異なるのではなく、LIFO の挙動による実装上の違いです。
よくある誤解とミスは何か？
1 つ目は、BFS があらゆる種類の最短経路問題を解くという誤解です。前述のとおり、BFS が保証するのは、重みなしグラフにおける辺の本数の最小値です。重みが異なる場合、ある移動が別の移動と同じ価値を持つとは限らないため、問題モデル自体が変わります。 algs4.cs.princeton.edualgs4.cs.princeton.edu
2 つ目は、DFS は常に BFS より少ないメモリを使用するという仮定です。訪問済み配列と探索状態を含めると、どちらのアルゴリズムも一般に の追加空間を使用します。キューまたはスタックの最大サイズは、特定のグラフ形状や実装によって異なる場合がありますが、漸近計算量だけから、どちらか一方に無条件の優位性があるとはいえません。 ocw.mit.edu
3 つ目は、再帰 DFS があらゆる入力に対して安全だという考えです。非常に長い深さを持つグラフでは、再帰の深さも大きくなります。言語と実行環境の呼び出しスタック制限を考慮する必要があり、そのような場合には明示的なスタックを用いる反復実装のほうが実用的なことがあります。また、再帰の呼び出しスタックが DFS の追加空間の一部であることも理解しておく必要があります。 ocw.mit.edu
4 つ目は、有向グラフを無向グラフであるかのように扱うことです。A から B への辺が存在しても、B から A へ移動できるとは限りません。入力を隣接リストに格納する際、無向グラフでは通常、両方の頂点のリストに辺を追加しますが、有向グラフでは始点の頂点のリストにだけ追加します。この違いは、到達可能性、連結性、閉路の意味を変えます。 ocw.mit.edu
5 つ目は、探索結果を一意の正しい経路と誤解することです。同じ最小本数の辺からなる経路が複数存在する場合、BFS は親ポインタを通じてそのうち 1 つを記録します。DFS も隣接頂点の順序によって異なる経路を生成できます。経路自体に優先順位が必要なら、ソート規則や追加条件を問題で指定する必要があります。
問題に応じて選ぶ際の基準は何か？
まず、目的を言葉にすることが最善です。問いが「開始点から到達できるか」だけであれば、BFS と DFS のどちらも可能であり、実装環境や後続で必要な解析に基づいて選べます。「同一の移動を何回行えば到着できるか」のように、辺の本数が最小であることが必要なら、BFS が自然な選択です。構造を解析しながら経路を深くたどる必要がある場合や、戻るタイミングが重要な場合は、DFS が適している可能性が高いです。
次に、辺が何を意味するかを確認します。すべての移動のコストが同じか、時間、距離、費用などの重みが関係するかを判断してください。重みが存在する場合、BFS の最短経路性をそのまま適用してはいけません。また、グラフが有向か、閉路があり得るか、グラフ全体を調べる必要があるかも、あらかじめ確認します。 ocw.mit.edualgs4.cs.princeton.edu
選択基準は次のようにまとめられます。
| 状況または問い | 最初に検討する手法 | 注意すべき条件 |
|---|---|---|
| 最小移動回数、レベルごとの拡張 | BFS | 辺のコストが等しい必要がある |
| 単純な到達可能性 | BFS または DFS | 開始頂点から到達可能な部分だけを探索する |
| グループとしての連結成分の発見 | DFS または BFS | 未訪問の各頂点に対して探索を繰り返す |
| 閉路、トポロジカル順序、強連結構造の解析 | DFS ベースの手法 | トポロジカルソートは DAG でのみ可能 |
| 時間やコストが異なる最短経路 | 別の重み付き最短経路手法 | 標準 BFS の保証は適用されない |
最後に、入力サイズと表現を考慮します。疎グラフには、隣接リストと BFS・DFS の標準的な の解析が適しています。再帰の深さが問題になる可能性がある環境では、反復 DFS を検討してください。訪問順序が採点や業務ルールに影響する場合、隣接リストの順序も設計の一部です。
結論：名前より探索の目的と条件が重要
BFS と DFS は、グラフを網羅的に探索するための異なる戦略です。BFS はキューを使って近い頂点から探索範囲を広げ、重みなしグラフで辺の本数が最小の経路を提供できる強みがあります。DFS は再帰またはスタックを使って 1 つの枝を深く探索してバックトラックし、連結成分、閉路、DAG におけるトポロジカルソートなど、グラフ構造を扱う多くの手法の基礎になります。 ocw.mit.edualgs4.cs.princeton.edu
どちらも訪問済みマーカーを必要とし、隣接リストを使う場合には一般に同じ漸近時間計算量を持ちます。したがって、両者を選ぶ鍵は、速度のような単一のラベルではありません。最短経路を何によって定義するか、辺に重みがあるか、方向と閉路をどのように解釈するか、グラフ全体を処理する必要があるかです。これらの条件を先に区別すれば、BFS と DFS を適切な目的に使えます。