深度优先搜索

深度优先搜索（DFS）是一种用于遍历或搜索树或图的算法。这个算法会尽可能深地搜索树的分支。当节点v的所在边都已被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个过程反复进行直到所有节点都被访问为止。

可以将其想象成在走一个巨大的迷宫。你选择一条路，一直走到底，直到遇到死胡同。然后，你退回到上一个路口，选择一条你还没走过的路，继续走到尽头。

你不断重复这个过程，直到探索完所有可能的路径。这种“一条路走到黑，不撞南墙不回头”的策略，就是深度优先搜索的核心思想。

1. DFS 的核心机制

DFS 的实现主要有两种方式：递归和手动模拟栈。递归是其中最自然、最常用也最容易理解的方式。

1.1 递归实现

递归完美地契合了 DFS “深入”和“回溯”的特性。一个递归函数调用自身，就是在向更深一层探索；当这个函数执行完毕返回时，就是在“回溯”到上一层。

一个标准的递归 DFS 函数通常包含以下几个部分：

1. 递归边界 (Base Case)：定义递归何时停止。这可能是找到了目标，或者走到了一个无法再前进的“死胡同”。
2. 处理当前层逻辑：在当前节点（或当前状态）下进行一些操作，例如记录路径、更新答案等。
3. 标记状态：在进入下一层递归之前，通常需要标记当前节点“已访问”，以防止在图中（尤其是有环的图）反复进入同一个节点，导致无限循环。
4. 递归调用 (Recursive Step)：遍历当前节点可以到达的所有相邻且未被访问过的节点，并对它们分别进行递归调用。
5. 撤销标记（回溯）：当从一个节点的递归调用返回后，可能需要将之前做的标记撤销。这一步非常关键，尤其是在求解排列、组合等需要探索所有可能解路径的问题中。这个过程被称为“回日志”。

1.2 图的表示方法

在对图进行 DFS 之前，我们需要先在程序中把图存储起来。最常见的两种方式是邻接矩阵和邻接表。

1.2.1 邻接矩阵

使用一个二维数组 g[N][N] 来存图，其中 g[i][j] 表示节点 $i$ 和节点 $j$ 之间是否存在边。

• 优点：查询两个点之间是否有边非常快，时间复杂度为 $O(1)$。
• 缺点：空间复杂度高达 $O(N^2)$，其中 $N$ 是节点数量。当节点数量很多，但边相对稀疏时，会造成巨大的空间浪费。

// 适用于 N 较小的情况，例如 N <= 500
int g[501][501]; 
int n, m; // n个点, m条边

void add(int u, int v) {
  // 无向图
  g[u][v] = 1;
  g[v][u] = 1;
}

1.2.2 邻接表

使用一个数组，数组的每个元素是一个动态数组（vector）或链表，g[i] 存储了所有与节点 $i$直接相连的节点。

• 优点：空间复杂度为 $O(N+M)$，其中 $N$ 是节点数， $M$ 是边数。对于稀疏图（$M$ 远小于 $N^2$）非常节省空间。这是在算法竞赛中最常用的方式。
• 缺点：查询两个点之间是否有边，需要遍历其中一个点的邻接表，效率稍低。

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

// N 通常可以开到 1e5 或更大
vector<int> g[100001];
int n, m; // n个点, m条边

void add(int u, int v) {
  g[u].push_back(v);
  g[v].push_back(u); // 无向图需要加两条边
}

1.3 基础 DFS 模板

下面是一个基于邻接表的经典图遍历 DFS 模板。

题意概括：从节点1开始，深度优先遍历整个图，并打印出访问的节点顺序。

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

const int N = 100005;
vector<int> g[N];
bool vis[N]; // 标记数组，vis[i] = true 表示 i 节点已被访问
int n, m;

// 核心DFS函数
// u: 当前正在访问的节点
void dfs(int u) {
    vis[u] = true; // 标记当前节点已访问
    cout << u << " "; // 处理当前节点逻辑（这里是打印）

    // 遍历 u 的所有邻居 v
    for (int v : g[u]) {
        if (!vis[v]) { // 如果邻居 v 没有被访问过
            dfs(v);    // 继续深入访问 v
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m; // n个点, m条边
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    // 从节点1开始遍历
    // 如果图不一定是连通的，需要一个循环来确保所有节点都被访问
    // for (int i = 1; i <= n; ++i) {
    //   if (!vis[i]) dfs(i);
    // }
    dfs(1);

    return 0;
}

代码解释：

• g[N] 是邻接表，vis[N] 是访问标记数组，这是 DFS 的标配。
• dfs(int u) 函数是递归的核心。它首先标记当前节点 u 已访问，然后遍历 u 的所有邻居 v。如果 v 尚未被访问，就对其发起新的 dfs 调用，这实现了“深入”。
• 当 for 循环结束，意味着从 u 出发的所有路径都已探索完毕，dfs(u) 函数随之结束并返回，这实现了“回溯”。

复杂度分析：

• 时间复杂度：$O(N+M)$。其中 $N$ 是节点数，$M$ 是边数。在使用邻接表的情况下，每个节点只会被访问一次（因为有 vis 数组），每条边也只会被访问两次（在无向图中，从 u 到 v 一次，从 v 到 u 一次）。所以总的时间消耗与节点数和边数之和成正比。
• 空间复杂度：$O(N)$。主要开销来自邻接表（$O(M)$）、vis 数组（$O(N)$）以及递归调用栈的深度。在最坏情况下（例如一个链状的图），递归深度可能达到 $N$，所以空间复杂度为 $O(N+M)$。通常我们简化为 $O(N)$，因为 $M$ 在稀疏图中与 $N$ 是同个数量级。

2. DFS 的应用与变种

DFS 不仅仅是图的遍历工具，它的思想可以用来解决一大类搜索问题。

2.1 连通块与 Flood Fill

题意概括：给定一个 $R \times C$ 的二维字符矩阵，其中 '#' 代表障碍物，'.' 代表空地。计算矩阵中有多少个由 '.' 组成的连通块。一个 '.' 和它上下左右的 '.' 属于同一个连通块。

这本质上是计算图的连通分量个数。每个 '.' 是一个节点，相邻的 '.' 之间有边。

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

char g[101][101];
bool vis[101][101];
int r, c;
int dx[] = {0, 0, 1, -1}; // 方向数组，方便地表示上下左右
int dy[] = {1, -1, 0, 0};

// 从(x, y)开始进行深度优先搜索
void dfs(int x, int y) {
    vis[x][y] = true; // 标记(x, y)已访问

    // 尝试四个方向
    for (int i = 0; i < 4; ++i) {
        int nx = x + dx[i];
        int ny = y + dy[i];

        // 检查新坐标是否越界，是否是障碍物，是否已访问
        if (nx >= 0 && nx < r && ny >= 0 && ny < c && g[nx][ny] == '.' && !vis[nx][ny]) {
            dfs(nx, ny); // 继续搜索
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> r >> c;
    for (int i = 0; i < r; ++i) {
        for (int j = 0; j < c; ++j) {
            cin >> g[i][j];
        }
    }

    int ans = 0; // 连通块数量
    for (int i = 0; i < r; ++i) {
        for (int j = 0; j < c; ++j) {
            // 如果找到一个新的、未被访问的 '.'
            // 说明发现了一个新的连通块
            if (g[i][j] == '.' && !vis[i][j]) {
                ans++;
                dfs(i, j); // 将这个连通块里所有的 '.' 都标记为已访问
            }
        }
    }
    
    cout << ans << endl;

    return 0;
}

代码解释：

• 主函数中的两层循环遍历整个网格。
• 每当遇到一个我们从未访问过的 '.'，我们就找到了一个新的连通块的“入口”。此时，连通块数量 ans 加一。
• 然后，从这个“入口”开始调用 dfs(i, j)。这个 dfs 函数会像洪水一样（这也就是 Flood Fill 这个名字的由来）蔓延到所有与 (i, j) 相连通的 '.'，并将它们全部标记为 vis[...][...] = true。
• 这样，当我们外层循环再次遇到这个连通块里的其他 '.' 时，会因为 vis 数组的判断而跳过，从而保证了每个连通块只被计数一次。

复杂度分析：

• 时间复杂度：$O(R \times C)$。每个格子最多被访问一次。
• 空间复杂度：$O(R \times C)$。用于存储地图和 vis 数组，以及递归栈的深度。

2.2 全排列问题

题意概括：给定一个正整数 $n$，输出 $1$ 到 $n$ 的所有排列。

这个问题可以看作一个搜索问题：我们在第1个位置放哪个数？第2个位置放哪个数？... 第 $n$ 个位置放哪个数？这就构成了一棵搜索树。

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

const int N = 10;
int p[N];     // 存放当前排列
bool used[N]; // used[i] = true 表示数字 i 已经被使用
int n;

// k: 当前正在确定第 k 个位置的数
void dfs(int k) {
    // 递归边界：如果已经处理到第 n+1 个位置，说明前n个位置已填满
    if (k > n) {
        for (int i = 1; i <= n; ++i) {
            cout << p[i] << " ";
        }
        cout << endl;
        return; // 结束当前分支的搜索
    }

    // 遍历 1 到 n，尝试将每个可用的数放入第 k 个位置
    for (int i = 1; i <= n; ++i) {
        if (!used[i]) { // 如果数字 i 还没被用过
            p[k] = i;       // 将 i 放入第 k 个位置
            used[i] = true; // 标记 i 已被使用

            dfs(k + 1);     // 递归地去确定第 k+1 个位置

            // 回溯！
            // 当从 dfs(k + 1) 返回时，说明基于“第k位放i”的所有排列都已搜索完毕。
            // 我们需要撤销刚才的选择，去尝试下一个可能的i。
            used[i] = false; 
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    dfs(1); // 从第1个位置开始搜索

    return 0;
}

代码解释：

• dfs(k) 的作用是确定排列中第 k 个位置的数字。
• p 数组用来存储当前正在构建的排列。
• used 数组是状态标记，用来确保每个数字在单个排列中只出现一次。
• 回溯是这个实现中最关键的一步。在 dfs(k + 1) 返回之后，执行 used[i] = false;。这一步操作的意义是：我们已经探索完了“在第k位放置数字i”的所有可能性，现在我们要收回这一步选择，回到“第k位尚未放置任何数”的状态，以便 for 循环可以继续尝试将下一个可用的数字（比如 i+1）放在第k位。如果没有这一步回溯，那么当 i=1 的分支结束后，used[1] 将永远为 true，导致后续的分支无法再使用数字1。

复杂度分析：

• 时间复杂度：$O(n! \times n)$。一共有 $n!$ 个排列，每生成一个排列需要 $O(n)$ 的时间（在 k>n 的判断中打印输出）。
• 空间复杂度：$O(n)$。递归栈的深度为 $n$，以及 p 和 used 数组的空间。

2.3 路径寻找

题意概括：在一个迷宫中，给定起点 'S' 和终点 'E'，判断是否存在一条从 'S' 到 'E' 的路径。

这是 DFS 最直接的应用之一。

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

char g[101][101];
bool vis[101][101];
int r, c;
int sx, sy, ex, ey; // 起点和终点坐标
bool ok = false; // 标志是否找到路径

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

void dfs(int x, int y) {
    if (ok) return; // 剪枝：如果已经找到路径，后续搜索无需进行
    vis[x][y] = true;

    if (x == ex && y == ey) {
        ok = true;
        return;
    }

    for (int i = 0; i < 4; ++i) {
        int nx = x + dx[i];
        int ny = y + dy[i];

        if (nx >= 0 && nx < r && ny >= 0 && ny < c && g[nx][ny] != '#' && !vis[nx][ny]) {
            dfs(nx, ny);
            if (ok) return; // 剪枝
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> r >> c;
    for (int i = 0; i < r; ++i) {
        for (int j = 0; j < c; ++j) {
            cin >> g[i][j];
            if (g[i][j] == 'S') { sx = i; sy = j; }
            if (g[i][j] == 'E') { ex = i; ey = j; }
        }
    }

    dfs(sx, sy);

    if (ok) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}

代码解释：

• 这个 dfs 的目标是“找到终点”。dfs(x, y) 的含义是“尝试从 (x, y) 出发看能否到达终点”。
• 当 x == ex && y == ey 条件满足时，说明我们已经到达终点，将标志 ok 设为 true 并立即返回。
• 剪枝：一旦 ok 变为 true，意味着我们已经成功找到了一条路径，任何后续的搜索都变得没有意义。因此，在 dfs 函数的入口和递归调用返回后都检查 ok 的状态，如果为 true 就立刻终止当前的搜索和返回，这可以节省大量不必要的计算。

复杂度分析：

• 时间复杂度：$O(R \times C)$。每个格子最多访问一次。
• 空间复杂度：$O(R \times C)$。

2.4 拓扑排序 (针对有向无环图 DAG)

概念：在一个有向无环图 (Directed Acyclic Graph, DAG) 中，拓扑排序是对其顶点的一种线性排序，使得对于每一条有向边 $(u, v)$，顶点 $u$ 都排在顶点 $v$ 的前面。

应用：常用于解决具有依赖关系的任务调度问题。例如，编译代码时，文件A依赖于文件B，那么必须先编译B再编译A。

DFS思路：拓扑排序的结果与 DFS 的“完成时间”密切相关。一个节点 $u$ 的 DFS 过程结束（即从 dfs(u) 返回）的时刻，我们称之为 $u$ 的完成时间。可以证明，在 DAG 中，一条边 $(u,v)$ 的起点 $u$ 的完成时间一定晚于终点 $v$ 的完成时间。因此，所有节点按照其完成时间的逆序排列，就是一个拓扑序列。

题意概括：给定一个 $N$ 个点 $M$ 条边的有向无环图，输出其任意一个拓扑序列。

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

const int N = 100005;
vector<int> g[N]; // 存有向图
vector<int> ans;  // 存放拓扑序列
int vis[N];       // 访问状态：0=未访问, 1=正在访问, 2=已完成访问
int n, m;

// 返回值表示是否发现环
bool dfs(int u) {
    vis[u] = 1; // 标记为正在访问

    for (int v : g[u]) {
        if (vis[v] == 0) { // 如果邻居未被访问
            if (dfs(v)) return true; // 如果在子树中发现了环，直接返回
        } else if (vis[v] == 1) {
            // 如果遇到了一个正在访问的节点，说明有环
            return true;
        }
    }
    
    vis[u] = 2; // 标记为已完成访问
    ans.push_back(u); // 将 u 加入结果列表
    return false; // 未发现环
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v); // 有向边 u -> v
    }

    for (int i = 1; i <= n; ++i) {
        if (vis[i] == 0) {
            if (dfs(i)) {
                cout << "Graph has a cycle!" << endl;
                return 0;
            }
        }
    }

    // ans 中是完成时间的顺序，拓扑序是其逆序
    reverse(ans.begin(), ans.end());
    for (int node : ans) {
        cout << node << " ";
    }
    cout << endl;

    return 0;
}

代码解释：

• vis 数组使用了三种状态来同时完成拓扑排序和环的检测：
  • 0 (未访问): 初始状态。
  • 1 (正在访问): dfs(u) 已被调用，但尚未返回。这表示 $u$ 在当前递归栈中。
  • 2 (已完成访问): dfs(u) 及其所有后代节点的访问都已结束。
• 环检测：如果在访问 $u$ 的邻居 $v$ 时，发现 vis[v] == 1，这意味着我们从 $u$ 出发，经过若干条边，又回到了当前递归路径上的一个祖先节点 $v$，形成了一个环。
• 拓扑序列生成：当一个节点 u 的所有邻居都已被探索完毕（即 for 循环结束），dfs(u) 即将返回。此时是 u 的完成时间点。我们把 u 加入到 ans 列表的末尾。因为后完成的节点在拓扑序中更靠前，所以最后将整个 ans 列表反转即可得到正确的拓扑序。

复杂度分析：

• 时间复杂度：$O(N+M)$。每个节点和每条边都只访问一次。reverse 操作的复杂度是 $O(N)$。
• 空间复杂度：$O(N+M)$。用于邻接表、vis 数组和递归栈。

3. DFS 与 BFS 的对比

特性	深度优先搜索 (DFS)	广度优先搜索 (BFS)
数据结构	栈 (Stack)，通常通过递归隐式实现	队列 (Queue)
搜索方式	一条路走到黑，然后回溯	一层一层地向外扩展
路径结果	找到的路径不一定是最短的	在无权图中，找到的路径一定是最短的
空间消耗	与最长路径（递归深度）有关，比较节省空间	与图的最大宽度有关，可能非常消耗空间
适用场景	寻找是否存在路径、全排列、拓扑排序、寻找所有解	寻找最短路径（无权图）、层序遍历
实现方式	递归或手动栈	迭代 + 队列

明确 DFS 的状态：在设计 DFS 函数时，首先要思考清楚函数需要哪些参数来唯一确定当前的状态。例如，在全排列中是 dfs(k)，k 代表当前处理的位置；在迷宫中是 dfs(x, y)，(x, y) 代表当前坐标。

管理好 visited 状态：visited 数组是防止无限循环和重复计算的关键。对于不需要回溯的纯遍历问题（如求连通块），标记为 true 后就不再更改。对于需要探索所有路径的问题（如全排列），则需要在回溯时撤销标记。

注意递归深度：DFS 的递归实现简洁优美，但在某些极端情况下（如图退化成一条长链），递归深度可能非常大，导致“栈溢出”(Stack Overflow)。在这种罕见的情况下，可能需要用手动栈的方式来将递归转化为迭代。

剪枝优化：在搜索过程中，如果能判断出当前分支不可能产生更优的解或合法的解，就应该提前终止这个分支的搜索。这被称为“剪枝”，是优化搜索算法性能的关键技巧。