深度优先搜索（DFS）

DFS的介绍

DFS（深度优先搜索，Depth-First Search）是一种用于遍历或搜索树或图的算法。
它从一个节点开始，尽可能深地搜索树的分支，直到到达叶子节点（没有子节点的节点），然后回溯到上一个节点，继续搜索其他分支。
这个过程会一直进行，直到所有可能的分支都被探索完毕。

工作原理

DFS的工作原理可以总结为以下几个步骤

选择一个起始节点：从树或图的某个节点开始。
探索尽可能深的分支：从当前节点开始，选择一个未被访问过的邻接节点，然后递归地在该节点上执行DFS。
回溯：当当前节点的所有邻接节点都被访问过，或者到达了叶子节点时，回溯到上一个节点。
重复：重复步骤2和3，直到所有节点都被访问过。

DFS的特点

栈的使用：在实现DFS时，通常使用栈数据结构来存储节点。在递归实现中，调用栈隐式地充当了栈的角色。
时间复杂度：对于有V个顶点和E条边的图，DFS的时间复杂度通常是O(V + E)。
空间复杂度：在最坏的情况下，DFS的空间复杂度也是O(V)，因为可能需要存储整个路径上的节点。
路径搜索：DFS非常适合于寻找从起点到终点的路径，尤其是在图不是非常大的情况下。
连通性问题：DFS可以用来检测图的连通性，例如，检查一个图是否是强连通的。

图示示例

下面是一个简单的图示：

节点1为根节点，也叫起始节点
DFS 示例树结构，节点 1 为起始根节点

那么节点1向下遍历，直到遍历到第一个没有子节点的节点4
DFS 从节点 1 沿分支深入至叶子节点 4
因为4已经没有子节点，已经是叶子节点，所以无法再向下遍历，所以回溯到上一个它的父节点3，并对节点4作标记，节点3接着向下遍历未被标记的子节点5
访问节点 4 后回溯至节点 3，并继续访问节点 5
因为5同样是叶子节点，遍历有到达了最深层，所以继续回溯到父节点3，同时标记5，我们发现3也没有未被标记的子节点了，无法再向下遍历，那么3接着向上回溯到父节点2，同时对3作标记，继续遍历2的未被标记的子节点6

接下来过程：2→6→7，节点7向上回溯到6并标记，节点6向下遍历子节点，6→8,然后连续向上回溯 8→6→2→1 直到回溯到根节点1,发现有可以向下遍历的子节点
DFS 遍历节点 2 的子树并逐层回溯至根节点
接着按照上述模式进行剩余的遍历，完成整张图的遍历，图的序号即为遍历的顺序
DFS 完成整棵树遍历的访问顺序

DFS 代码模板

下面用邻接表存图，并从给定起点开始遍历。进入节点时立刻标记，可以防止无向图沿同一条边反复递归。

#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t;
using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t;

vector<vector<int>> g;
vector<bool> vis;

void dfs(int u) {
    vis[u] = true;
    cout << u << ' ';
    for (int v : g[u]) {
        if (!vis[v]) dfs(v);
    }
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, s;
    cin >> n >> m >> s;
    g.resize(n + 1);
    vis.assign(n + 1, false);
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(s);
    cout << '\n';
    return 0;
}

例题辨析：马的遍历

洛谷 P1443 马的遍历要求的是起点到每个位置的最少步数。DFS 会先沿某一条分支不断深入，第一次到达某个位置时并不能保证路径最短；如果为了修正答案而允许反复访问，又会产生数量巨大的重复搜索。

因此，这道题不应该把 DFS 穷举当作提交方案。所有移动的代价都相同，BFS 会按照距离一层一层扩展，某个位置第一次入队时就已经得到最短距离。完整解法见宽度优先搜索（BFS）。

例题：AtCoder ABC325 C Sensors

题目链接：AtCoder ABC325 C Sensors

网格中的**#**表示传感器。上下、左右或斜向相邻的传感器属于同一个连通块，求网格中一共有多少个传感器连通块。

从任意一个尚未访问的传感器出发，DFS能够访问与它连通的全部传感器。搜索结束以后，这一整个连通块都已经被标记。因此遍历网格时，每遇到一个未访问的**#**，答案加$1$并进行一次DFS即可。

题目的网格最多包含$10^6$个位置，最坏情况下递归深度也可能很大。下面使用显式栈实现迭代DFS，避免调用栈溢出。

点击展开完整代码

/* Fufffh */
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t;
using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int h, w;
    cin >> h >> w;
    vector<string> s(h);
    for (string &row : s) cin >> row;
    vector<vector<bool>> vis(h, vector<bool>(w));
    int ans = 0;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) if (s[i][j] == '#' && !vis[i][j]) {
            ans++;
            stack<pair<int, int>> st;
            st.push({i, j});
            vis[i][j] = true;
            while (!st.empty()) {
                auto [x, y] = st.top(); st.pop();
                for (int dx = -1; dx <= 1; dx++) {
                    for (int dy = -1; dy <= 1; dy++) {
                        int nx = x + dx, ny = y + dy;
                        if (nx < 0 || nx >= h || ny < 0 || ny >= w || s[nx][ny] != '#' || vis[nx][ny]) continue;
                        vis[nx][ny] = true;
                        st.push({nx, ny});
                    }
                }
            }
        }
    }
    cout << ans << '\n';
    return 0;
}

每个格子至多入栈一次，时间复杂度和空间复杂度均为$O(hw)$。

例题：洛谷 P1706 全排列问题

题目链接：洛谷 P1706 全排列问题

按照字典序输出$1$到$n$的所有排列，每个数字在同一排列中恰好出现一次。

图遍历中的DFS通常在访问节点后永久标记；枚举方案时则不同。设当前正在填写排列的第$d$个位置，依次尝试每个尚未使用的数字$x$：

选择$x$并标记；
递归填写下一个位置；
回到当前层后撤销标记，再尝试其他数字。

这就是回溯中最常见的“选择—递归—撤销”。因为每层都按照从小到大的顺序尝试数字，生成的排列自然符合字典序。

点击展开完整代码

/* Fufffh */
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t;
using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t;

int n, a[10];
bool used[10];

void dfs(int d) {
    if (d > n) {
        for (int i = 1; i <= n; i++) cout << setw(5) << a[i];
        cout << '\n';
        return;
    }
    for (int x = 1; x <= n; x++) if (!used[x]) {
        a[d] = x;
        used[x] = true;
        dfs(d + 1);
        used[x] = false;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    dfs(1);
    return 0;
}