競プロノート

Appearance

DFS（深さ優先探索） ​

グラフを深さ優先で探索するアルゴリズム。

到達可能性の判定、連結成分の探索、木の走査などに利用する。

特徴 ​

項目内容
用途グラフ探索・到達可能性・連結成分
計算量O(V+E)
空間計算量O(V+E)（グラフを含む）

実装 ​

cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m, s;
    cin >> n >> m >> s;
    vector<vector<int>> g(n);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
    }

    vector<bool> visited(n);
    vector<int> dist(n, -1);
    auto dfs = [&](auto dfs, int v) -> void {
        visited[v] = true;
        for (int nv : g[v]) {
            if (visited[nv]) continue;
            dist[nv] = dist[v] + 1;
            dfs(dfs, nv);
        }
    };
    dist[s] = 0;
    dfs(dfs, s);

    for (int v = 0; v < n; v++) cout << dist[v] << '\n';
}

使用例 ​

基本形 ​

cpp
vector<bool> visited(n);
vector<int> dist(n, -1);

auto dfs = [&](auto dfs, int v) -> void {
    visited[v] = true;
    for (int nv : g[v]) {
        if (visited[nv]) continue;
        dist[nv] = dist[v] + 1;
        dfs(dfs, nv);
    }
};

dist[0] = 0;
dfs(dfs, 0);

連結成分を数える ​

無向グラフを想定する。

cpp
vector<bool> visited(n);
auto dfs = [&](auto dfs, int v) -> void {
    visited[v] = true;
    for (int nv : g[v]) {
        if (!visited[nv]) dfs(dfs, nv);
    }
};

int cnt = 0;
for (int v = 0; v < n; v++) {
    if (visited[v]) continue;
    dfs(dfs, v);
    cnt++;
}

注意点 ​

  • visited[v] = true は訪問時に設定する。
  • 通常のDFSでは探索後に visited[v] = false に戻さない。
  • DFSの dist は探索木の深さであり、一般グラフの最短距離とは限らない。最短距離ならBFSを使う。
  • 再帰が深くなるとスタックオーバーフローする可能性がある。
  • visited を使わないと、閉路のあるグラフで無限再帰する可能性がある。

DFSとバックトラックの違い ​

通常のDFSでは訪問済みを保持する。

一方、すべての単純パスを列挙するなどのバックトラックでは、再帰から戻るときに訪問状態を解除する。

cpp
auto dfs = [&](auto&& dfs, int v) -> void {
    visited[v] = true;

    for (int nv : g[v]) {
        if (visited[nv]) continue;
        dfs(dfs, nv);
    }

    visited[v] = false; // バックトラック
};

この場合は通常のDFSと異なり、計算量が指数時間になることもある。

関連 ​

  • BFS
  • DFS全探索
  • サイクル検出
  • 木DP