DFS — 深さ優先探索アルゴリズムをわかりやすく解説

深さ優先探索（DFS）は、木やグラフを探索するときに、まず1本の経路を行けるところまで進み、行き止まりになったら戻るアルゴリズムです。簡単に言うと、DFSは進めるだけ深く進み、進めなくなったら別の分岐があった場所まで戻ります。

1つだけ覚えるなら、これです。DFSとは「まず深く進み、それから戻る」探索です。

深さ優先探索がすること

DFSは木にも一般のグラフにも使えます。1つのノードから始めて、未訪問の隣接ノードへ次々に移動します。未訪問の隣接ノードがなくなったら、1つ前のノードに戻って探索を続けます。

この「戻る」動きこそがDFSの特徴です。再帰で実装すると、関数呼び出しのスタックが自動的にそれを処理します。反復で実装する場合は、明示的なスタックが同じ役割を果たします。

DFSには、いつでも同じになる唯一の訪問順序があるわけではありません。実際の順序は、隣接ノードをどの順番で見るかに依存します。

たとえば、あるノードの隣接ノードが $B$ と $C$ なら、先に $B$ を訪れる場合と先に $C$ を訪れる場合で、DFSの順序は変わることがあります。それでもどちらもDFSです。ルールは同じで、「兄弟の分岐を見る前に、まず深く進む」からです。

次のような接続を持つグラフを考えます。

隣接ノードは常に左から右の順に調べ、開始点は $A$ とします。

DFSは次のように進みます。

したがって、DFSの訪問順序の一例は次のとおりです。

A, B, D, E, C, F

大事なのは、DFSが $A \to B$ 側を終えてから $A \to C$ 側に進むことです。隣接ノードの順番を変えれば、訪問順序も変わることがあります。

DFSでは、行き止まりに達したあとにどこへ戻るかを覚えておく仕組みが必ず必要です。だからDFSではスタックが自然に登場します。

再帰版のDFSでは、各関数呼び出しが探索の続きを待ちながら積み重なり、バックトラックすると逆順に戻っていきます。反復版のDFSでは、ノードをスタックに積み、直近の未完了地点から再開するときに取り出します。

グラフが隣接リストで表され、各頂点を最初に訪れたときに訪問済みとして記録するなら、DFSの実行時間は、到達可能な部分に対して

O(V + E)

です。ここで $V$ は頂点数、 $E$ は辺の数です。

追加で必要な空間は通常

O(V)

です。訪問済み管理のための構造と、再帰スタックまたは明示的なスタックのどちらも、頂点数に応じて大きくなりうるからです。

一般のグラフでは、訪問済みチェックを忘れると、DFSが閉路を永遠に回り続けることがあります。木を無向グラフとして表している場合でも、コード側で明示的に処理していないなら、親ノードへすぐ戻る動きを避ける必要があります。

DFSは経路を1つ見つけることはできますが、重みなしグラフで最短経路を保証するわけではありません。最短経路が目的で、すべての辺の重みが同じなら、通常はBFSから考えるのが適切です。

順序は隣接ノードの並びに依存します。その順番が変われば、探索順序も変わることがあります。

DFSは、単に近い順に調べるよりも、構造を深くたどって調べたいときに役立ちます。よくある用途は次のとおりです。

DFSがよく登場する主な理由は、「まず深く進み、それから戻る」という考え方が、多くの再帰的な問題構造に自然に合うからです。

DFSはまず1本の分岐を深くたどります。BFSは、ある距離にあるすべてのノードを調べてから、次の距離へ進みます。

網羅的な探索や再帰的な構造を重視するなら、DFSは自然な選択です。重みなしグラフで最短経路を重視するなら、まずはBFSを選ぶほうが安全なことが多いです。

6個のノードを持つ小さなグラフを描き、隣接ノードの順番を固定してみましょう。DFSを手で実行して、いつ前に進み、いつバックトラックしたかを正確に書き出してみてください。隣接ノードの順番を並べ替えたあとで訪問順序が変わっても、それはバグではありません。DFSの性質の一部です。

問題をアップロードすると、検証済みのステップバイステップ解答が数秒で届きます。