深さ優先探索（DFS）完全解説：再帰・反復実装から応用・SCC・トポロジカルソートまで

2025年11月20日 最終更新日時 : 2025年11月20日 エバープレイ編集部

深さ優先探索法（Depth-First Search: DFS）とは

深さ優先探索（DFS）は、グラフや木構造を探索するための基本的なアルゴリズムの一つです。根（あるいは任意の開始頂点）から出発して可能な限り「深く」進み、行き止まりに達したら一つ前に戻って別の未訪問の道を探索する、という手続きに基づきます。再帰的な実装が自然で、バックトラッキングや多くのグラフアルゴリズム（連結成分の検出、サイクル検出、トポロジカルソート、強連結成分の抽出など）の基礎として用いられます。

基本的な動作原理

グラフ G = (V, E) に対して、DFS は次のように動作します。

  • 始点 v を訪問（visited に登録）し、隣接頂点を順に見ていく。
  • 隣接頂点 u が未訪問なら、u に対して再帰的に DFS を呼び出す（深く進む）。
  • すべての隣接頂点を調べ終えたら、呼び出し元へ戻る（バックトラック）。

複数の連結成分を持つ場合は、未訪問の頂点が残っていれば別の始点から DFS を開始し、グラフ全体をカバーします（DFS フォレスト）。

再帰実装と反復実装（スタック）

典型的な再帰実装（擬似コード）:

function DFS(v):
    visited[v] = true
    for each u in adj[v]:
        if not visited[u]:
            DFS(u)

再帰は直感的で簡潔ですが、実行環境によってはスタックオーバーフロー（深さが大きい場合）を招きます。再帰が使えない／避けたい場合は明示的なスタックを用いた反復実装を行います。

function DFS_iterative(start):
    stack = empty stack
    push start
    while stack not empty:
        v = pop stack
        if not visited[v]:
            visited[v] = true
            for each u in adj[v]:
                if not visited[u]:
                    push u

反復実装ではどのタイミングで visited を記録するか（push 時か pop 時か）で挙動が変わるので、重複訪問を防ぐために push 時に訪問済みフラグを立てることが一般的です。

計算量と空間量

  • 時間計算量: 隣接リスト表現なら O(|V| + |E|)。各頂点は一度訪問され、各辺は少なくとも一度だけ考慮されます。隣接行列表現では O(|V|^2) になります。
  • 空間計算量: 再帰深度や明示的なスタックで O(|V|)。加えて隣接リストや visited 配列で O(|V| + |E|) の補助記憶が必要です。
  • 最悪ケースの再帰深さはグラフのパス長に依存し、直線状のグラフでは O(|V|) になります。

エッジ分類と発見/終了時刻（時間刻印）

有向グラフに対する DFS では、アルゴリズム実行中に各頂点に「発見時刻（discovery time）」と「終了時刻（finish time）」を割り当てることができ、これにより辺を次のように分類できます。

  • 木辺（tree edge）: DFS 木に属する辺。
  • 後退辺（back edge）: 子から祖先へ向かう辺。これはサイクルの存在を示唆する。
  • 前方辺（forward edge）: 木辺でないが祖先へ向かう辺（有向グラフのみ）。
  • 交差辺（cross edge）: 異なる部分の探索間をつなぐ辺（有向グラフのみ）。

無向グラフでは、上記のうち実質的に木辺と後退辺だけが発生します（無向辺は双方向なので forward/cross の区別は意味を成しません）。発見/終了の時間刻印はトポロジカルソートや強連結成分解析で重要になります。

代表的な応用例

  • 連結成分の検出（無向グラフ）
  • サイクル検出（有向・無向両方） — 有向グラフでは back edge の検出で O(|V|+|E|) で実現可能
  • トポロジカルソート — DAG 上で各頂点の終了時刻の降順に並べる方法
  • 強連結成分（SCC）の抽出 — Kosaraju のアルゴリズム（2 回の DFS）、Tarjan のアルゴリズム（1 回の DFS、low-link を利用）
  • 橋（bridge）・関節点（articulation point）の検出 — low 値を用いる Tarjan 系手法
  • 迷路やパズルの探索（バックトラッキング）や探査順の記録
  • 組合せ最適化での深さ優先的な探索（枝刈りを伴う）

トポロジカルソートと DFS の関係

DAG（有向非巡回グラフ）に対して DFS を行い、各頂点の終了時刻（finish time）を記録しておきます。終了時刻の降順に頂点を並べると、それがトポロジカル順序になります。これは、ある辺 u→v があるとき、u の終了時刻は常に v の終了時刻より後になる（finish[u] > finish[v]）という DFS の性質に基づきます。

強連結成分（SCC）と関連アルゴリズム

代表的手法:

  • Kosaraju 法: 1) 任意順に DFS を行い各頂点の終了時刻を記録。2) 辺の向きを反転したグラフで、終了時刻の降順に DFS を行う。各 DFS によって得られる集合が SCC。計算量 O(|V|+|E|)。
  • Tarjan 法: 1 回の DFS でスタックと low-link 値を用いて SCC を検出。これも O(|V|+|E|)。

実装上の注意点と落とし穴

  • 訪問フラグの扱い: 追加で push するときに visited を付けるか、取り出したときに付けるかで重複処理や順序が変わります。重複 push を避けるなら push 時に visited を立てるのが安全です。
  • 再帰深度制限: Python 等では再帰深度のデフォルト制限（1000）に注意。深いグラフでは sys.setrecursionlimit を使うか、反復版（スタック）にする。
  • 入力サイズと表現: 稀に隣接行列を使うと O(|V|^2) の計算になり大規模グラフでは実用的でない。疎グラフでは隣接リストを使う。
  • 有向/無向の違い: サイクル判定やエッジ分類の解釈が異なるため実装時に注意。
  • 探索順序の影響: 隣接リスト内の隣接順序やスタック／再帰の実装により訪問順が変わり、たとえばトポロジカルソートの結果が一意でない場合がある。

変種と拡張

  • 反復深化深さ優先探索（IDDFS）: 深さ制限付き DFS を深さを 0 から増やしながら繰り返す手法。BFS のような浅い解を見つける性質（最短距離）を、DFS の低いメモリ消費で得られる。探索木の分岐が有限である場合に有効。
  • 制約充足問題やパズルでは、DFS に枝刈り（枝刈り条件やヒューリスティクス）を導入して計算量を削減するのが一般的。
  • ランダム化 DFS: グラフ探索で異なる経路を得たい場合に隣接順序をランダムにすることがある（例: 迷路生成アルゴリズムの一つとしてのランダム DFS）。

実用的なノウハウ

  • 大規模グラフでは隣接リストの使用、メモリと時間のトレードオフを検討する。
  • 再帰実装が簡潔だが、スタックオーバーフローの危険があるなら反復実装へ切替える。
  • 並列処理: DFS 自体は逐次的で並列化が難しい場合が多い。広い探索空間で分岐ごとに作業を分散する手法はあるが、同期や重複検出が課題になる。
  • デバッグ: 発見/終了時刻やスタックの状態、visited 配列をログ出力すると挙動が追跡しやすい。

具体的なコード例（Python、簡易）

再帰版（隣接リスト adj を想定）:

def dfs(v, adj, visited):
    visited[v] = True
    for u in adj[v]:
        if not visited[u]:
            dfs(u, adj, visited)

反復版（スタック）:

def dfs_iter(start, adj):
    visited = [False] * len(adj)
    stack = [start]
    while stack:
        v = stack.pop()
        if not visited[v]:
            visited[v] = True
            for u in adj[v]:
                if not visited[u]:
                    stack.append(u)

まとめ

深さ優先探索（DFS）は、シンプルで多用途な探索手法です。時間計算量は O(|V|+|E|)（隣接リストの場合）と効率的であり、トポロジカルソート、サイクル検出、強連結成分の検出、橋や関節点の発見、バックトラッキングを要する問題など多数の応用を持ちます。一方で深さが大きくなれば再帰的実装のスタックオーバーフローや、探索順に依存する結果の差違など実装上の注意点も存在します。用途や環境に応じて再帰／反復、データ表現（隣接リスト/行列）、または IDDFS 等の変種を使い分けることが重要です。

参考文献

カテゴリー
IT
前の記事
レベル順探索(BFS)とは何か？概要・実装・応用・最短経路の復元まで徹底解説New!!
2025年11月20日
次の記事
反復深化探索（IDDFS/IDS）徹底ガイド：仕組み・計算量・完全性・最適性と実装のコツNew!!
2025年11月20日