深さ優先探索（DFS）とは？仕組み・コード・計算量をわかりやすく解説

DFSが解く問題

DFSは、1つの枝を最後まで調べ尽くしてから次の枝に移ることで、「ここから何に到達できるか」という問いに答えます。この順序は、経路の長さよりも経路の構造が重要な場面で役立ちます。たとえば、迷路の出口を探す、グラフに閉路があるか調べる、互いに依存するタスクを並べる、パズルの解をすべて列挙する、といった場面です。

幅優先探索と違い、DFSは最短経路を見つけません。その代わり、メモリに保持するのは現在の経路だけで済み、ノードに入った時点と処理を終えた時点を自然に記録できるという強みがあります。

考え方を言葉で説明すると

1. 現在のノードを訪問済みにします。
2. 未訪問の隣接ノードごとに、そのノードに移動し、そこから手順1を繰り返します。
3. 未訪問の隣接ノードがなくなったノードは「完了」です。来たノードに戻ります。
4. 開始ノードに戻り、未訪問の隣接ノードがなければ探索は終了です。

前のノードに戻ることをバックトラッキングと呼びます。再帰を使えば、コールスタックが自動的にこれを行ってくれます。

具体例で一歩ずつ確認

BFSの記事と同じ無向グラフを使います。A–B、A–C、B–D、C–D、C–E、D–F。A から始め、隣接ノードはアルファベット順に試します。

訪問順は A, B, D, C, E, F、完了順は E, C, F, D, B, A です。トポロジカルソートや強連結成分分解のアルゴリズムで使うのは、この完了順です。

Pythonでの実装

再帰版が最も短く、考え方にいちばん近い書き方です。

def dfs(graph, node, visited=None):
    if visited is None:
        visited = []
    visited.append(node)
    for nxt in graph[node]:
        if nxt not in visited:
            dfs(graph, nxt, visited)
    return visited
graph = {
    "A": ["B", "C"], "B": ["A", "D"], "C": ["A", "D", "E"],
    "D": ["B", "C", "F"], "E": ["C"], "F": ["D"],
}
print(dfs(graph, "A"))  # ['A', 'B', 'D', 'C', 'E', 'F']

リストを使うと例は読みやすくなりますが、in による判定が O(n) になります。大きなグラフでは、所属判定用に別途 set を持たせてください。反復版は明示的なスタックを使うため、Pythonの再帰上限を避けられます。隣接ノードを逆順に積むことで、元の順序で取り出せます。

def dfs_iterative(graph, start):
    visited, order = set(), []
    stack = [start]
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        order.append(node)
        for nxt in reversed(graph[node]):
            if nxt not in visited:
                stack.append(nxt)
    return order
print(dfs_iterative(graph, "A"))  # ['A', 'B', 'D', 'C', 'E', 'F']

BFSとの違いに注意してください。ここではノードを取り出すときに訪問済みにするため、同じノードがスタックに複数回入ることがあります。これはDFSでは正しい動作で、本来の深さ優先の順序が保たれます。

有向グラフの閉路検出

DFSの代表的な応用では、各ノードを白（未訪問）、灰（現在の経路上）、黒（完了）の3色で塗り分けます。灰色のノードに到達したら、現在の経路に戻る辺があるということなので、閉路が存在します。

def has_cycle(graph):
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {node: WHITE for node in graph}
    def visit(node):
        color[node] = GRAY
        for nxt in graph[node]:
            if color[nxt] == GRAY:
                return True              # back edge
            if color[nxt] == WHITE and visit(nxt):
                return True
        color[node] = BLACK
        return False
    return any(color[n] == WHITE and visit(n) for n in graph)
print(has_cycle({"a": ["b"], "b": ["c"], "c": ["a"]}))  # True
print(has_cycle({"a": ["b"], "b": ["c"], "c": []}))     # False

時間計算量と空間計算量

バリエーションとよくある間違い

• 行きがけ順と帰りがけ順：ノードに入るときに記録するのが行きがけ順（pre-order）、完了するときに記録するのが帰りがけ順（post-order）です。有向非巡回グラフでは、帰りがけ順の逆順がトポロジカル順序になります。
• 連結成分：まだ訪問していないノードのたびに新しいDFSを開始します。開始1回につき連結成分が1つ見つかります。
• 反復深化DFS：深さ制限を 0, 1, 2, … と増やしながらDFSを実行します。BFSのように最短経路を見つけつつ、DFSの少ないメモリで済みます。
• グリッド上のフラッドフィル（ペイントツールのバケツ塗りつぶし）は、同じ色の隣接マスに対するDFSまたはBFSです。

そのほかのよくあるバグは次のとおりです。訪問済み集合を忘れる（閉路があると無限ループになります）、visited=[] のような変更可能なデフォルト引数を使う（呼び出し間で共有されてしまいます）、無向辺で親へ戻る辺を閉路と誤認する、です。

DFSを使う場面と実世界での用途

• DFSは、到達可能性の判定、閉路検出、トポロジカルソート、連結成分・強連結成分、橋と関節点、そしてバックトラッキングによる全探索に使います。
• 最小ステップ数が必要なときはBFSを、辺に重みがあるときはダイクストラ法やA*を使ってください。
• コーディング面接の問題：島の数、グラフの複製、コーススケジュール（閉路検出）、二分木のパス和、順列の生成など。
• 実世界：依存関係の順序を解決するビルドシステムやパッケージマネージャ、制御フローを解析するコンパイラ、迷路の生成、ファイルシステムやHTML文書の木の走査など。