深さ優先探索 (DFS)

Q: DFS の時間計算量は？

DFS は `O(V + E)` 時間で実行されます。ここで `V` は頂点数、`E` は辺の数です。各頂点を 1 回訪れ、各辺を 1 回見るためです。スタックと訪問済み集合に `O(V)` の空間を使います。

最終更新 2026年7月1日

深さ優先探索は、バックトラックする前に各枝をできるだけ深くたどってグラフを探索します。始点ノードから始めて、ある隣接ノードを訪れ、次にその隣接ノードを訪れ、というように行き止まり（未訪問の隣接ノードがないノード）に達するまで進み、そこで引き返して次の枝を試します。上の再生を押して、1 つの経路を下って底に到達し、また戻ってくる様子を見てみましょう。

DFS はスタックで自然に表現できます。明示的なスタック（ここでアニメーション化しているもの）でも、再帰による呼び出しスタックでも構いません。各ノードと辺を 1 回ずつ訪れるため、V 個の頂点と E 本の辺を持つグラフに対して O(V + E) 時間で実行されます。

時間計算量と空間計算量

指標	計算量	備考
時間	O(V + E)	各頂点と辺を 1 回ずつ訪れる
空間	O(V)	スタック + 訪問済み集合、最悪の場合すべてのノード
探索	最も深いものから	他より先に 1 つの枝を最後までたどる
データ構造	スタック（または再帰）	LIFO の順序が深さ優先の挙動を駆動する

ステップごと

ステップ	何が起こるか
1	始点ノードをスタックに積む。
2	ノードを取り出す。すでに訪問済みならスキップする。
3	訪問済みとして印を付け、それに到達した辺を記録する。
4	未訪問の隣接ノードをすべてスタックに積む。
5	スタックが空になるまで繰り返す。

具体例

グラフ A → [B, C]、B → [D]、C → [E] に対する A からの反復的 DFS。隣接ノードを列挙順に積む（LIFO スタックは最後に積んだものを先に取り出す）：

ステップ	スタック（右が先頭）	訪問済み	動作
1	`[A]`	`{}`	始点 `A` を積む。
2	`[B, C]`	`{A}`	`A` を取り出し、訪問済みにし、隣接ノード `B` 次に `C` を積む。
3	`[B, E]`	`{A, C}`	`C` を取り出し、訪問済みにし、隣接ノード `E` を積む。
4	`[B]`	`{A, C, E}`	`E` を取り出し、訪問済みにする。隣接ノードなし。
5	`[D]`	`{A, C, E, B}`	`B` を取り出し、訪問済みにし、隣接ノード `D` を積む。
6	`[]`	`{A, C, E, B, D}`	`D` を取り出し、訪問済みにする。スタックが空：完了。

DFS を使うべき場面

使うべき場面	避けるべき場面
閉路検出、トポロジカルソート、または連結成分の発見が必要なとき。	重みなしグラフで最短経路が必要なとき。それを行うのは BFS であって DFS ではない。
グラフが幅広く浅いため、スタックが多数のフロンティアノードを持つキューよりはるかに少ないメモリで済むとき。	グラフが非常に深く再帰を使うとき。呼び出しスタックがオーバーフローする可能性がある。
迷路解きやバックトラッキング探索のように、経路を網羅的に探索したいとき。	始点からの距離順にノードを発見する必要があるとき。
到達可能性、または 2 つのノード間に経路が存在するかを確認するとき。	見つけた経路上の辺の数を最小にすることを保証しなければならないとき。

Depth-First Searchのコード

Python, JavaScript, Java, C++, Cによるクリーンで実行可能なDepth-First Searchの実装です。言語を選んでコードをコピーするか、Coddyプレイグラウンドに読み込んだ状態で開けます。

PythonでのDepth-First SearchのコードPython
1def dfs(graph, node, visited):2    visited.add(node)3    order = [node]4    for neighbor in graph[node]:5        if neighbor not in visited:6            order.extend(dfs(graph, neighbor, visited))7    return order8
9
10graph = {11    "A": ["B", "C"],12    "B": ["D", "E"],13    "C": ["F"],14    "D": [],15    "E": ["F"],16    "F": [],17}18
19order = dfs(graph, "A", set())20print("DFS order:", " -> ".join(order))
このコードをPythonプレイグラウンドで実行

JavaScriptでのDepth-First SearchのコードJavaScript
1const graph = {2    A: ["B", "C"],3    B: ["D", "E"],4    C: ["F"],5    D: [],6    E: ["F"],7    F: [],8};9
10function dfs(node, visited = new Set(), order = []) {11    if (visited.has(node)) return order;12    visited.add(node);13    order.push(node);14    for (const next of graph[node]) {15        dfs(next, visited, order);16    }17    return order;18}19
20console.log("DFS from A:", dfs("A").join(" -> "));
このコードをJavaScriptプレイグラウンドで実行

JavaでのDepth-First SearchのコードJava
1import java.util.List;2
3public class Main {4    static List<List<Integer>> adj = List.of(5        List.of(1, 2),    // neighbors of 06        List.of(0, 3, 4), // neighbors of 17        List.of(0, 5),    // neighbors of 28        List.of(1),9        List.of(1, 5),10        List.of(2, 4)11    );12    static boolean[] visited = new boolean[6];13
14    static void dfs(int node) {15        visited[node] = true;16        System.out.print(" " + node);17        for (int next : adj.get(node)) {18            if (!visited[next]) dfs(next);19        }20    }21
22    public static void main(String[] args) {23        System.out.print("DFS from 0:");24        dfs(0);25        System.out.println();26    }27}
このコードをJavaプレイグラウンドで実行

C++でのDepth-First SearchのコードC++
1#include <iostream>2#include <vector>3
4void dfs(int node, const std::vector<std::vector<int>>& adj,5         std::vector<bool>& visited) {6    visited[node] = true;7    std::cout << node << " ";8    // Recurse into every unvisited neighbor9    for (int next : adj[node]) {10        if (!visited[next]) dfs(next, adj, visited);11    }12}13
14int main() {15    // 6-node undirected graph as an adjacency list16    std::vector<std::vector<int>> adj = {17        {1, 2},     // 018        {0, 3, 4},  // 119        {0, 5},     // 220        {1},        // 321        {1, 5},     // 422        {2, 4},     // 523    };24    std::vector<bool> visited(adj.size(), false);25    std::cout << "DFS from node 0: ";26    dfs(0, adj, visited);27    std::cout << "\n";28    return 0;29}
このコードをC++プレイグラウンドで実行

CでのDepth-First SearchのコードC
1#include <stdbool.h>2#include <stdio.h>3
4#define N 65
6// 6-node undirected graph as an adjacency matrix7int adj[N][N] = {8    {0, 1, 1, 0, 0, 0},9    {1, 0, 0, 1, 1, 0},10    {1, 0, 0, 0, 0, 1},11    {0, 1, 0, 0, 0, 0},12    {0, 1, 0, 0, 0, 1},13    {0, 0, 1, 0, 1, 0},14};15bool visited[N];16
17void dfs(int node) {18    visited[node] = true;19    printf("%d ", node);20    // Recurse into every unvisited neighbor21    for (int next = 0; next < N; next++) {22        if (adj[node][next] && !visited[next]) dfs(next);23    }24}25
26int main(void) {27    printf("DFS from node 0: ");28    dfs(0);29    printf("\n");30    return 0;31}
このコードをCプレイグラウンドで実行

深さ優先探索のよくある質問

DFS の時間計算量は？

DFS は O(V + E) 時間で実行されます。ここで V は頂点数、E は辺の数です。各頂点を 1 回訪れ、各辺を 1 回見るためです。スタックと訪問済み集合に O(V) の空間を使います。

DFS と BFS の違いは？

DFS はスタックを使い、バックトラックする前に 1 つの枝を深く潜りますが、BFS はキューを使い、近いノードから順に階層ごとに探索します。BFS は重みなしグラフで最短経路を見つけますが、DFS は見つけません。ただし DFS は幅広いグラフでメモリ使用量が少なく、閉路検出やトポロジカルソートのようなタスクに自然です。

DFS は再帰的ですか、反復的ですか？

どちらも使えます。再帰版はプログラムの呼び出しスタックを暗黙的に使い非常に簡潔です。反復版は明示的なスタック（ここのアニメーションのように）を使い、大きなグラフでの深い再帰によるスタックオーバーフローを避けられます。

BFS ではなく DFS を使うべきなのはいつ？

経路全体を探索する必要があるときに DFS を使います。閉路検出、トポロジカルソート、連結成分、迷路解きのようなバックトラッキング探索などです。スタックは一度に 1 つの枝のフロンティアしか保持しないため、幅広いグラフでメモリ使用量も少なくなります。重みなしグラフで最短経路が必要なとき、または始点からの距離順のノードが必要なときは BFS を使いましょう。

DFS は最短経路を見つけられますか？

確実には見つけられません。DFS はたまたま最初に見つけた経路を返しますが、それは多くの場合、辺の数が最小の経路ではありません。均等に広がるのではなく深く潜ることに専念するからです。重みなしグラフの最短経路には BFS を、重み付きグラフには Dijkstra のアルゴリズムを使いましょう。

なぜ DFS には訪問済み集合が必要なのですか？

訪問済み集合がないと、DFS は複数の経路で到達できるノードを再訪し、閉路のあるグラフでは無限ループに陥ります。ノードを取り出すときに訪問済みとして印を付け（訪問済みの取り出しはスキップし）ることで、各ノードが 1 回だけ処理されることが保証され、実行時間が O(V + E) に保たれます。よくある誤りは、取り出すときにのみ訪問済みにしつつ重複を積み続けることです。これは正しいですが、スキップすべき古いエントリがスタックに残ることがあります。