深さ優先探索（DFS）完全ガイド：擬似コード・計算量・実装上の注意点と応用例をわかりやすく解説
エバープレイ編集部深さ優先探索（Depth-First Search：DFS）とは
深さ優先探索（DFS）は、グラフや木構造を探索するための基本的なアルゴリズムの一つです。探索を始めた頂点（ノード）から可能な限り深く枝をたどり、行き止まりに達したら最後に分岐した地点に戻って未探索の枝を探索する、という「深さ優先」の戦略を取ります。再帰的な実装が直感的で一般的ですが、明示的なスタックを使った反復実装でも表現できます。
基本的な動作イメージ
典型的なDFSの振る舞いは次のようになります。
- 開始ノードから出発する。
- 未訪問の隣接ノードがあればそこへ移動し、さらにその先へ進む（再帰的に）。
- 行き止まり（未訪問の隣接ノードが無い）に達したら一段戻り、別の未訪問の隣接ノードを探索する。
- すべてのノードが訪問されるか、探索条件（目的のノードの発見など）が満たされるまで続ける。
木とグラフでの違い
木構造（有向／無向問わずルートが定まるもの）に対するDFSは比較的単純です。親子関係が明確なので訪問済みチェックは親への戻りだけで済む場合があります。一方、一般のグラフでは「サイクル（閉路）」が存在するため、同じ頂点を何度も訪れる無限ループに陥らないように訪問済みマーク（visited配列や集合）を持つことが必須です。
擬似コード（再帰版と反復版）
再帰版とスタックを使った反復版の典型的な擬似コードを示します。ここではグラフは隣接リストで表され、ノードの集合をV、辺の集合をEとします。
（再帰版）
procedure DFS_recursive(v):
visited[v] = true
for each u in adj[v]:
if not visited[u]:
DFS_recursive(u)
（反復版：明示的なスタック）
procedure DFS_iterative(start):
stack = empty stack
push(start, stack)
visited[start] = true
while stack not empty:
v = pop(stack)
for each u in adj[v]:
if not visited[u]:
visited[u] = true
push(u, stack)
反復版ではノードをプッシュする順序（隣接リストの走査順）により探索結果の順序が変わります。再帰版は関数呼び出しスタックがそのまま探索経路を管理します。
計算量（時間・空間）
- 時間計算量：隣接リスト表現では O(|V| + |E|)。各頂点は一度だけ訪問され、各辺は探索中に一度ずつ調べられます。隣接行列表現だと O(|V|^2) になります。
- 空間計算量：訪問済み配列などで O(|V|)。再帰呼び出しの深さ（もしくはスタックの最大サイズ）は最悪でグラフの高さ（あるいは頂点数）に依存し O(|V|) になります。
DFSが得意な問題・用途
- 到達可能性の判定（ある頂点から別の頂点へ到達できるか）
- 連結成分の列挙（無向グラフ）
- トポロジカルソート（有向非巡回グラフ：DAG）— DFSの終了時刻を用いる方法が代表的
- 閉路（サイクル）検出（有向グラフでは白灰黒法、無向グラフでは親確認）
- 強連結成分（SCC）の検出（Kosaraju法やTarjan法はいずれも DFS を基礎にしている）
- バックトラッキングを使う探索（パズル、ナップサックの列挙、8クイーン問題など）
- 迷路やパス探索の単純実装（最短経路保証はない）
トポロジカルソートとDFS
有向グラフのトポロジカルソートは、DFSで各ノードの「終了時刻（postorder）」を記録し、終了時刻の降順にノードを並べることで得られます。これは辺が常に先に始点の終了時刻よりも小さいことを利用しています。サイクルの存在（有向閉路）があればトポロジカルソートは存在しませんが、DFS中に後退辺（back edge）を見つければサイクルありと判定できます。
サイクル検出と色（white/gray/black）方式
有向グラフでのサイクル検出は次のように白・灰・黒の3色法で行うことが多いです。
- 白（未訪問）→ グレイ（探索中）→ 黒（探索終了）
- 探索中に隣接ノードがグレイであれば、現在のノードから先祖へ戻る辺が存在する＝サイクルがある（後退辺）。
DFSの変種・関連アルゴリズム
- Iterative Deepening DFS（IDDFS）：深さ制限付きDFSを増分的に深さを広げて実行する手法。メモリ効率が良く、深さが大きく分岐度が高い探索空間で最良の解深さを見つけるときに有効。BFSと同様に最短解（深さを基準）を得られ、メモリ消費はDFS並み。
- Tarjanの強連結成分アルゴリズム：単一DFSで各ノードの「lowlink」を計算しSCCを検出。線形時間O(|V|+|E|)。
- Kosaraju法：グラフとその逆辺グラフで2回のDFSを行いSCCを列挙。
- バックトラッキングのコア：DFSは探索木を自然に形成するため、探索空間の列挙や条件付き探索で中心的役割を果たす。
実装上の注意点と落とし穴
- 再帰深度の制約：深いグラフや線形チェーン状グラフでは再帰深度が大きくなり、言語のスタック制限でスタックオーバーフローを起こすことがある。必要に応じて反復版を使うか、再帰上限の調整が必要。
- 訪問済みチェックの忘れ：グラフのサイクルにより無限ループ（あるいは無限再帰）に陥るため、必ず visited チェックを入れる。
- 隣接リスト/行列の選択：疎なグラフでは隣接リストが効率的。稠密グラフでは行列でも構わないが時間計算量が変化することに注意。
- 多重辺や自己ループの扱い：探索アルゴリズムの意図によっては無視したり別扱いにする必要あり。
- 探索順序の影響：隣接リストのソート順や反復の順序によって探索経路や出力の順序は変わる。問題によっては順序を揃える必要がある（例：提出判定が順序依存の競技プログラミング等）。
- 最短経路には不向き：重み無しでも最短パスを求めるなら幅優先探索（BFS）が保証するので、DFSは最短保証が無い点に注意。
具体的な応用例（短い説明）
- コンパイラの依存解析：トポロジカルソートでコンパイル順序を決める。
- グラフの連結成分検出：ネットワーク分析やクラスタリングの前処理。
- 迷路やパズル解法：バックトラッキングによる解の列挙と検証。
- 静的解析・モデル検査：状態遷移系の全状態到達性チェックなど。
- ソーシャルネットワークやウェブクローリングの到達解析（ただし実際の大規模データではメモリ・並列処理など追加考慮が必要）。
DFSを使う場面の判断基準
DFSを選ぶかどうかは、目的と制約に依存します。到達可能性・連結成分・構造解析のように「全体を一度深くたどれば十分」な場合には有力です。一方、最短経路が必要であったり、広いが浅い探索空間で最短解が期待される場合にはBFSや他の手法が適切です。また、メモリが制約されている場合は再帰（もしくは反復のスタック）を使うDFSが有利になることがあります。
まとめ
深さ優先探索（DFS）は、アルゴリズム設計における基本かつ強力なツールです。単純な再帰実装で直感的に動作を理解しやすく、多くのグラフアルゴリズム（トポロジカルソート、SCC検出、バックトラッキング問題など）の基礎になっています。実装時はサイクル対策や再帰深度、データ表現（隣接リスト／行列）といった実務的な注意点を考慮することが重要です。
参考文献
- 深さ優先探索 - Wikipedia（日本語）
- Depth-first search - Wikipedia (English)
- Algorithm Tutor: Depth First Search
- Stack Exchange: DFS complexity explanation
- GeeksforGeeks: Depth First Search (DFS) for a Graph
- Cormen, Leiserson, Rivest, Stein - Introduction to Algorithms（一般的なアルゴリズム教科書）
投稿者プロフィール
