どちらもグラフをたどるための方法
幅優先探索(BFS)は近い層から、深さ優先探索(DFS)は一つの枝を進めるところまで進んでから戻ります。どちらも、頂点と辺の管理を正しく行えば始点から到達できる範囲を調べられます。ただし、訪問順と得られる追加の性質は違います。同じ「経路を探す」という要求でも、何か一つの経路があればよいのか、辺の本数が最小の経路が必要なのかで選択が変わります。有向か無向か、辺の重みをどう扱うかも先に定めます。探索という共通の名前だけで、すべての問題へ同じ答えを返す手順だとは考えないでください。
| 観点 | BFS | DFS |
|---|---|---|
| 基本の進め方 | 近い層から | 一つの枝を奥へ |
| 基本の保持 | キュー | 再帰・明示的スタック |
| 最小の辺数 | 標準形で保証 | 一般には保証しない |
同じ四頂点で順序を比べる
辺A→B、A→C、B→Dを持ち、隣接頂点をB、Cの順に見るとします。BFSはキューを使い、Aの次にB、C、最後にDを調べます。DFSはスタックや再帰を使い、A、B、Dまで進んでから戻り、Cを調べます。この順序は隣接頂点の列挙順にも依存するので、常に同じアルファベット順になるわけではありません。経路を返したい場合は、発見した頂点の前駆を記録します。訪問順の列と、始点からゴールへ連続する経路の列も別物です。A、B、C、Dと訪問しても、そのままの順序で辺がつながるとは限りません。
最短の辺数を保証するのはBFS
各辺を一歩として数える問題では、BFSは距離0、1、2の順に頂点を発見するため、初めて発見した距離を最短の辺数とできます。DFSでは、長い枝でゴールを先に見つけた後に、短い経路が残っていることがあります。ただしBFSの保証も、任意の重みの総和を最小にするものではありません。A→Dの重みが100、A→B→Dの二辺が各1なら、辺数と重みの目的は食い違います。重み付きの目的には、Dijkstra法やBellman–Ford法など条件に合う別の方法を選びます。何を最小にしたかを答えの説明へ明記してください。
閉路の検査には状態の違いが必要
どちらの探索でも、同じ頂点を何度も処理しないための発見済み管理が重要です。有向グラフのDFSで閉路を調べるなら、未発見、探索中、探索完了を区別する方式があります。探索中の祖先へ戻る辺は閉路を示しますが、探索を完了した頂点へ向かう辺だけでは閉路とは限りません。無向グラフでは親へ戻る辺の扱いも別に決めます。「訪問済みへ辺があれば必ず閉路」という単純な判定は使えません。トポロジカル順序など探索を応用する処理では、帰りがけの順序とDAGの前提も含めて確認します。
幅と深さの両方をメモリへ換算する
隣接リストで各頂点と辺を一定回数調べる標準形なら、時間はどちらもO(V+E)、発見状態や前駆を含む補助領域はO(V)です。BFSのキューは広い層を保持する場合があり、DFSのスタックは細長いグラフで深くなる場合があります。「DFSは常に定数メモリ」「BFSは必ずDFSより多い」という一律の比較はできません。再帰DFSには実行環境のスタック上限もあります。隣接行列なら辺を調べる費用も変わるので、表現とグラフの形を含めて評価します。最終的には、必要な保証、幅、深さ、経路の保持方法を合わせて選びます。