DFS（深さ優先探索）の仕組みを解説
深さ優先探索がバックトラックする前にできるだけ深く探索する仕組みを学びます。スタック、再帰、発見時刻と終了時刻、一般的な応用を理解します。
Traversal Algorithms
詳細な説明
深さ優先探索（DFS）
深さ優先探索は、バックトラックする前に一つのパスをできるだけ遠くまで辿ることでグラフを探索します。兄弟ノードを探索する前にグラフの深部に潜るため、BFSとは根本的に異なります。
DFSの動作原理
- 初期化 — 開始ノードをスタックにプッシュ（または再帰的に関数を呼び出し）し、訪問済みとしてマークします。
- ポップ — スタックの最上部のノードを取り出します。これが現在のノードです。
- 探索 — 未訪問の隣接ノードそれぞれをスタックにプッシュし、マークします。
- バックトラック — ノードに未訪問の隣接ノードがない場合、前のノードに戻ります。
- 繰り返し — スタックが空になるまで続けます。
発見時刻と終了時刻
再帰的DFSでは、各ノードに2つのタイムスタンプが付きます：
- 発見時刻 — ノードが最初に訪問されたとき
- 終了時刻 — すべての子孫が完全に探索されたとき
これらのタイムスタンプは、辺の分類（木辺、後退辺、前進辺、交差辺）やトポロジカルソートなどのアルゴリズムに不可欠です。
時間・空間計算量
- 時間: O(V + E)
- 空間: O(V)（訪問済みセットとコールスタック用）
応用
DFSは多くの重要なグラフアルゴリズムの基盤です：
- サイクル検出 — 後退辺（祖先への辺）がサイクルを示す
- トポロジカルソート — 終了時刻の逆順が有効なトポロジカル順序
- 連結成分 — 各未訪問ノードからDFSを実行してすべての成分を発見
- 強連結成分 — KosarajuまたはTarjanのアルゴリズムがDFSを基盤とする
ユースケース
DFSはコンパイラでの依存関係解決やデッドコード検出、ゲームAIでの決定木探索、迷路生成アルゴリズム、強連結成分の発見のためのネットワーク分析で広く使用されています。タスクスケジューリングやビルドシステムに不可欠なトポロジカルソートの基盤でもあります。