DFS（深度优先搜索）课堂笔记

---

一、DFS 基础概念

DFS（Depth-First Search，深度优先搜索） 是一种用于遍历或搜索图/树的算法，核心思想是**“不撞南墙不回头”：从起点出发，沿着一条路径尽可能深入，直到无法继续或达到目标，然后回溯**（退回上一步）尝试其他路径。

核心特点

• 递归实现：通常借助递归函数自动完成“深入-回溯”过程；
• 回溯机制：部分场景需要“撤销操作”以尝试其他分支（如求最短路径、方案数）；
• 适用场景：连通性判断、路径搜索、排列组合生成等。

---

二、DFS 的应用场景

2.1 迷宫问题

迷宫问题是 DFS 的经典应用，通常涉及连通性判断、最短路径、路径打印等需求。

2.1.1 迷宫最短路径（带回溯 + 剪枝）

需求：在 $n \times m$ 迷宫中，从起点 $(1,1)$ 走到终点 $(n,m)$，求最短路径长度（只能走 .，不能走障碍物）。

代码实现与详解：

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

const int N = 2e5 + 10;
int n, m, ans = 1e9;  // ans记录最短路径，初始化为极大值
int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};  // 方向数组：右、左、下、上
int vis[50][50];  // 标记数组：vis[x][y]=1表示(x,y)已访问
char c[50][50];   // 存储迷宫地图

// 函数含义：当前在(x,y)，从起点到这里已走step步
void dfs(int x, int y, int step) {
    // 剪枝1：如果当前步数已超过已知最短路径，直接返回（优化）
    if (step > ans) return;
    
    // 终止条件：到达终点(n,m)，更新最短路径
    if (x == n && y == m) {
        ans = min(ans, step);
        return;
    }
    
    // 遍历4个方向
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i], ny = y + dy[i];  // 下一个位置(nx, ny)
        // 边界判断 + 未访问 + 可通行
        if (nx >= 1 && nx <= n && ny >= 1 && ny <= m 
            && vis[nx][ny] == 0 && c[nx][ny] == '.') {
            vis[nx][ny] = 1;  // 标记为已访问
            dfs(nx, ny, step + 1);  // 递归深入
            vis[nx][ny] = 0;  // 回溯：撤销标记，尝试其他方向
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> c[i][j];
        }
    }
    vis[1][1] = 1;  // 起点标记为已访问
    dfs(1, 1, 1);   // 从(1,1)出发，初始步数1
    cout << ans;
    return 0;
}

关键知识点：

• 回溯：vis[nx][ny] = 0 是核心——递归返回后，必须撤销访问标记，否则其他路径无法再走该点；
• 剪枝：if (step > ans) return 能大幅减少无效搜索（如果当前步数已比已知最短路径长，无需继续）；
• 方向数组：用 dx[] 和 dy[] 简化4个方向的移动逻辑。

---

2.1.2 迷宫路径打印

需求：在迷宫中从起点 $(sx,sy)$ 走到终点 $(ex,ey)$，打印完整路径（若有解输出路径，无解输出 -1）。

代码实现与详解：

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

int n, m, a[25][25];  // a[x][y]=1表示可通行，0表示障碍物
int sx, sy, ex, ey;   // 起点(sx,sy)，终点(ex,ey)
int f = 0;  // 标记是否找到路径（f=1表示找到）
int dx[4] = {0, -1, 0, 1}, dy[4] = {-1, 0, 1, 0};  // 方向：左、上、右、下
int vis[25][25];  // 访问标记

// 函数含义：当前在(x,y)，cx是路径记录（用"0""1""2""3"表示方向）
void dfs(int x, int y, string cx) {
    // 终止条件：到达终点
    if (x == ex && y == ey) {
        f = 1;  // 标记找到路径
        // 打印路径：从起点开始，根据cx还原每一步
        cout << "(" << sx << "," << sy << ")";
        int xx = sx, yy = sy;
        for (int i = 0; i < cx.size(); i++) {
            int fx = cx[i] - '0';  // 提取方向（字符转数字）
            xx += dx[fx];
            yy += dy[fx];
            cout << "->(" << xx << "," << yy << ")";
        }
        cout << endl;
        return;
    }
    
    // 遍历4个方向
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        // 边界判断 + 未访问 + 可通行
        if (nx >= 1 && nx <= n && ny >= 1 && ny <= m 
            && vis[nx][ny] == 0 && a[nx][ny]) {
            vis[nx][ny] = 1;  // 标记已访问
            dfs(nx, ny, cx + to_string(i));  // 递归：记录当前方向（i转字符串）
            vis[nx][ny] = 0;  // 回溯
        }
    }
    return;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }
    cin >> sx >> sy >> ex >> ey;
    
    // 特判：起点本身不可通行
    if (a[sx][sy] == 0) {
        cout << "-1";
        return 0;
    }
    
    vis[sx][sy] = 1;  // 起点标记
    dfs(sx, sy, "");  // 初始路径为空
    
    if (!f) cout << -1;  // 未找到路径
    return 0;
}

关键知识点：

• 路径记录：用 string cx 存储每一步的方向（如 "0" 表示左，"1" 表示上），最终通过方向数组还原完整路径；
• 特判起点：若起点本身是障碍物，直接输出 -1；
• 多解处理：代码会打印所有可能路径（若需仅打印第一条，可在找到后 return 并终止递归）。

---

2.2 排列组合问题

DFS 可高效生成组合数（不考虑顺序）和全排列（考虑顺序），核心是通过递归控制“选数”逻辑。

2.2.1 组合数生成（从 $n$ 个数中选 $m$ 个，不重复、按升序）

需求：输入 $n$ 和 $m$，输出从 $1 \sim n$ 中选 $m$ 个数的所有组合（按升序排列，如 $n=5, m=3$ 时输出 "1 2 3"、"1 2 4" 等）。

代码实现与详解：

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

const int N = 2e5 + 10;
int n, m;

// 函数含义：已选 step 个数，上一个选的数是 pre，当前已选列表为 v
void dfs(int step, int pre, vector<int> v) {
    // 终止条件：已选 m 个数，输出组合
    if (step == m) {
        for (int i = 0; i < v.size(); i++) {
            cout << v[i] << " ";
        }
        cout << endl;
        return;
    }
    
    // 从 pre+1 开始选数（保证升序，避免重复）
    for (int i = pre + 1; i <= n; i++) {
        vector<int> v2 = v;  // 复制当前已选列表
        v2.push_back(i);     // 加入新选的数 i
        dfs(step + 1, i, v2);  // 递归：step+1，更新 pre 为 i
    }
}

int main() {
    cin >> n >> m;
    vector<int> v;
    dfs(0, 0, v);  // 初始：step=0，pre=0，已选列表为空
    return 0;
}

关键知识点：

• 升序保证：通过 pre 参数限制“下一个数必须比上一个大”，自然避免重复组合（如不会出现 "2 1 3"）；
• 动态数组传参：每次递归复制 vector（v2 = v），确保不同分支的已选列表互不干扰。

---

2.2.2 全排列生成（补充完整版）

需求：输入 $n$ 个整数，输出它们的所有全排列（按字典序）。

完整代码实现与详解：

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

const int N = 2e5 + 10;
int n, a[N];
int vis[N];  // 标记数组：vis[i]=1表示a[i]已被选入排列

// 函数含义：已选 step 个数，当前排列为 v
void dfs(int step, vector<int> v) {
    // 终止条件：已选 n 个数（全排列完成）
    if (step == n) {
        for (int i = 0; i < v.size(); i++) {
            cout << v[i] << " ";
        }
        cout << endl;
        return;
    }
    
    // 遍历所有数，尝试选未被选过的
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {  // 若a[i]未被选
            vis[i] = 1;  // 标记为已选
            v.push_back(a[i]);  // 加入排列
            dfs(step + 1, v);   // 递归
            v.pop_back();  // 回溯：从排列中移除
            vis[i] = 0;    // 回溯：撤销标记
        }
    }
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    sort(a + 1, a + 1 + n);  // 先排序，保证按字典序输出
    vector<int> v;
    dfs(0, v);  // 初始：step=0，排列为空
    return 0;
}

关键知识点：

• 字典序保证：先对数组 sort，再按顺序选数，自然输出字典序排列；
• 回溯双操作：v.pop_back()（移除排列末尾元素） + vis[i] = 0（撤销访问标记），确保其他分支可重新选该数；
• 标记数组：vis[i] 针对“位置 $i$”而非“数值 $a[i]$”，避免重复选同一个位置的数（即使有重复数值，也能正确处理）。

---

三、DFS 代码模板与核心要素

通用模板结构

// 1. 定义全局变量/数组（避免递归传参过多）
int 全局变量;
int 标记数组[];  // 用于回溯

// 2. DFS函数
void dfs(参数列表：当前状态、已选/已走信息) {
    // ① 终止条件：达到目标（如到达终点、选够数）
    if (终止条件) {
        处理结果（如输出、更新答案）;
        return;
    }
    
    // ② 剪枝（可选）：提前终止无效搜索
    if (剪枝条件) return;
    
    // ③ 遍历所有可能的分支（如方向、选数）
    for (遍历所有可能) {
        // ④ 合法性判断（边界、未访问、可通行等）
        if (合法) {
            标记状态（如vis=1、加入列表）;  // ⑤ 标记
            dfs(更新后的参数);  // ⑥ 递归深入
            撤销标记（如vis=0、移除列表）;  // ⑦ 回溯（关键！）
        }
    }
}

// 3. 主函数
int main() {
    输入数据;
    初始化（如vis=0、起点标记）;
    dfs(初始参数);
    输出结果;
    return 0;
}

核心要素总结

要素	作用
终止条件	递归的“出口”，避免无限递归（如到达终点、选够数）。
标记数组	记录“已访问/已选”状态，防止重复走/重复选（如 vis[x][y]）。
回溯	递归返回后“撤销标记”，让其他分支可尝试该状态（如 vis[x][y] = 0）。
剪枝	提前终止无效搜索（如“当前步数 > 已知最短路径”），优化效率。

---

四、剪枝技巧

剪枝是 DFS 优化的核心，常见剪枝方式：

1. 最优性剪枝：如迷宫最短路径中，if (step > ans) return（当前路径已比已知最优解长，无需继续）；
2. 可行性剪枝：如判断“剩余未选数不足以凑够 $m$ 个”，提前终止；
3. 重复状态剪枝：若不同路径到达同一状态且结果相同，可记录该状态的结果，避免重复搜索（记忆化搜索）。

---

五、对比与总结

场景	是否需要回溯	关键思路	时间复杂度
迷宫连通性判断	否	只需标记访问，无需撤销	$O(n \times m)$
迷宫最短路径	是	回溯+最优性剪枝	较高（视剪枝效果）
组合数生成	否（传参复制）	限制“下一个数 > 上一个数”	$O(C(n,m))$
全排列生成	是	回溯+标记数组	$O(n!)$