GESP 7级

DFS 递归搜索

7级 · DP/图论/搜索

📖 一句话理解

DFS（Depth-First Search，深度优先搜索）就像走迷宫：沿着一条路一直走到底，走不通了就退回来，换一条路继续走。它用递归实现，是搜索类问题的基础。
💡 为什么重要？
DFS是搜索算法的基石。排列、组合、子集、连通性判断、路径搜索……几乎所有需要"枚举所有可能"的问题都可以用DFS解决。掌握DFS的"做选择→递归→撤销选择"框架，你就掌握了搜索类问题的万能模板。
📋 前置知识
  • 递归：函数调用自己，知道递归终止条件（base case）
  • for循环：基本的循环结构
  • 数组/向量：用 vector<int> 或 int[] 存储数据
  • swap函数：交换两个变量的值

🧠 DFS的核心框架

📐 DFS万能框架
void dfs(当前状态) {
  if (到达终点) {
    处理答案; // 比如输出、记录
    return;
  }
  for (每个选择) {
    做选择; // 比如标记已使用
    dfs(新状态); // 递归探索
    撤销选择; // 回溯！
  }
}

三个关键要素

🔑 必须搞清楚的三件事
  1. 状态（参数）：当前搜索到了什么位置？比如"已经选了前pos个元素"
  2. 终止条件：什么时候停下来？比如"所有位置都选完了"
  3. 选择与回溯：每个位置有哪些选择？选了之后要撤销，才能试下一个选择

🔢 例1：全排列

给定 [1,2,3]，输出所有排列。

📊 搜索树（想象一棵树）

从空开始：
├── 选1 → 选2 → 选3 → 得到 [1,2,3]
├── 选1 → 选3 → 选2 → 得到 [1,3,2]
├── 选2 → 选1 → 选3 → 得到 [2,1,3]
├── 选2 → 选3 → 选1 → 得到 [2,3,1]
├── 选3 → 选1 → 选2 → 得到 [3,1,2]
└── 选3 → 选2 → 选1 → 得到 [3,2,1]
共 3! = 6 种排列

💻 全排列代码（逐行注释）
#include <iostream>
#include <vector>
#include <algorithm>  // swap()
using namespace std;

int n;
vector<int> path;       // 存当前正在构建的排列
vector<bool> used;      // used[i] = true 表示数字i已经被选过了
vector<vector<int>> result;  // 存所有合法排列

void dfs() {
    // 终止条件：path的长度等于n，说明所有位置都选完了
    if (path.size() == n) {
        result.push_back(path);  // 把当前排列加入答案集合
        return;
    }

    // 尝试每个还没被用过的数字
    for (int i = 1; i <= n; i++) {
        if (!used[i]) {          // 如果数字i还没被使用
            used[i] = true;      // 做选择：标记为已使用
            path.push_back(i);   // 做选择：加入当前排列

            dfs();               // 递归：继续选下一个位置

            path.pop_back();     // 撤销选择：从排列中移除
            used[i] = false;     // 撤销选择：标记为未使用
        }
    }
}

int main() {
    n = 3;
    used.assign(n + 1, false);  // 初始化used数组（下标1~n）
    dfs();

    // 输出所有排列
    for (auto& p : result) {
        for (int x : p) cout << x << " ";
        cout << endl;
    }
    return 0;
}

🔢 例2：子集枚举

给定 [1,2,3]，输出所有子集（2³=8个）。

💻 子集枚举代码
#include <iostream>
#include <vector>
using namespace std;

int n = 3;
vector<int> path;        // 当前子集
vector<vector<int>> result;

void dfs(int start) {
    // 每个状态都是一个合法子集（包括空集）
    result.push_back(path);

    // 从start开始，保证不重复（如 [1,2] 和 [2,1] 视为相同）
    for (int i = start; i <= n; i++) {
        path.push_back(i);    // 做选择：加入i
        dfs(i + 1);           // 递归：下一个从i+1开始（避免重复）
        path.pop_back();      // 撤销选择：移除i
    }
}

int main() {
    dfs(1);
    // 输出所有子集
    for (auto& s : result) {
        cout << "{ ";
        for (int x : s) cout << x << " ";
        cout << "}" << endl;
    }
    return 0;
}

🔑 DFS vs BFS 对比

📝 DFS和BFS的区别
  • DFS：沿着一条路走到底再回溯，用递归（或栈）实现。适合找所有方案、判断连通性。
  • BFS：逐层扩展，用队列实现。适合求最短路径（无权图）。

简单记忆：DFS走迷宫是一条路走到黑，BFS是像水波一样一圈圈扩散。

🚨 易错点

⚠️ 常见错误汇总
  1. 忘记回溯（撤销选择）：这是最最常见的错误！递归返回后，必须把状态恢复原样，否则会影响后续分支。
  2. 终止条件写错：全排列是 path.size()==n，子集是每一步都记录结果。终止条件决定搜索是否正确。
  3. 递归参数传递错误：比如子集枚举要用 start 参数避免重复，忘记传递会导致重复方案。
  4. 没有visited数组：全排列必须记录哪些数字用过，否则同一个数字会被选多次。
  5. 递归深度太大：DFS是递归实现的，如果搜索深度太大（比如n>1000），可能会栈溢出。
  6. 剪枝不到位：DFS的效率靠"剪枝"提升——提前排除不可能的分支，否则指数级时间会超时。

🎯 练习建议

📝 循序渐进练习路径
  1. 先理解框架：把上面的"做选择→递归→撤销选择"框架抄下来，每次写DFS前先套这个框架。
  2. 手动模拟：在纸上画搜索树，手动模拟递归过程。
  3. 经典题目：
    • P1706 全排列（洛谷入门）
    • P7827 小朋友的数字（组合枚举）
    • P1443 马的遍历（BFS，但先练DFS理解搜索）
    • P1219 八皇后问题（经典DFS剪枝）
  4. 学会剪枝：在搜索过程中提前判断"这条路不可能有答案"就直接返回，可以大幅提升效率。
← 上一个：区间DP 📖 返回主目录 下一个：BFS 层序遍历 →