GESP 7级 · DFS递归搜索

📖概念讲解

【考点 · 7级】DFS递归搜索 — 深度优先搜索 + 递归实现

DFS（Depth-First Search）是搜索算法的基础。核心思路：沿着一条路走到黑，走不通再回头。用递归实现时，每次选一个未访问的邻居递归深入，回溯时撤销状态。

🔑 关键要素：

递归出口：找到目标 / 走到边界就 return
状态标记：visited 数组防止重复访问（不标记会死循环！）
状态恢复（回溯）：如果需要枚举所有方案，递归回来要 undo
剪枝：提前排除不可能的分支，大幅加速

DFS vs BFS：DFS 用栈（递归调用栈），走深不走广；BFS 用队列，层层展开。考试常考：全排列、子集、迷宫搜索、连通块计数。

💻代码示例

#include <iostream>
#include <vector>
using namespace std;
const int N = 5;
int grid[N][N];         // 迷宫地图：0=通路, 1=墙
bool vis[N][N];        // 标记数组：是否已访问
int dx[] = {0,0,-1,1};  // 四个方向：上下左右
int dy[] = {-1,1,0,0};
// DFS: 从 (x,y) 出发能否到达终点 (ex,ey)
bool dfs(int x, int y, int ex, int ey) {
    if (x == ex && y == ey) return true;  // 出口：到达终点
    vis[x][y] = true;         // 标记当前点已访问
    for (int i = 0; i < 4; i++) { // 枚举四个方向
        int nx = x + dx[i], ny = y + dy[i]; // 下一个位置
        if (nx<0||nx>=N||ny<0||ny>=N) continue; // 越界剪枝
        if (grid[nx][ny]==1||vis[nx][ny]) continue; // 墙或已访问剪枝
        if (dfs(nx, ny, ex, ey)) return true; // 递归深入
    }
    return false;              // 此路不通，回溯
}
int main() {
    // 构建迷宫
    int maze[N][N] = {
        {0,0,1,0,0},{0,1,0,0,1},{1,0,0,1,0},
        {0,0,0,0,0},{1,1,0,1,0}};
    for(int i=0;i<N;i++) for(int j=0;j<N;j++) grid[i][j]=maze[i][j];
    if (dfs(0, 0, 4, 4)) // 从 (0,0) 搜到 (4,4)
        cout << "可以到达！" << endl;
    else
        cout << "到不了…" << endl;
    return 0;
}
// 输出：可以到达！

🧩互动小测

❓ 问题1：DFS遍历图时，如果不使用 visited 数组标记，最可能的结果是？

❓ 问题2：DFS递归实现本质上利用了什么数据结构？

❓ 问题3：关于回溯，以下哪项说法正确？

🏋️动手练一练

📝 编程练习：全排列

给定一个正整数 n（1 ≤ n ≤ 8），输出 1~n 的所有全排列。每行一种排列，数字之间用空格分隔。

提示：用 DFS + 回溯。维护一个 path[] 数组和 used[] 布尔数组。used[i] 表示数字 i 是否已放入排列中。递归时依次尝试每个未使用的数字，放入后标记，递归下一层，递归返回后撤销标记（回溯）。

参考答案：

#include <iostream>
using namespace std;

int n, path[9];
bool used[9];

void dfs(int depth) {
    if (depth == n) {                   // 所有位置都填完了
        for (int i = 0; i < n; i++)
            cout << path[i] << " ";
        cout << endl;
        return;
    }
    for (int i = 1; i <= n; i++) {      // 枚举 1~n 每个数字
        if (used[i]) continue;          // 已用过就跳过
        path[depth] = i;                // 放入当前位
        used[i] = true;                 // 标记已使用
        dfs(depth + 1);                 // 递归填下一位
        used[i] = false;                // 回溯：撤销标记
    }
}

int main() {
    cin >> n;
    dfs(0);
    return 0;
}

要点：关键在于回溯时 used[i] = false; 这一行——如果忘了撤销，后面的分支就少枚举了数字，结果不全。

📝易错点提醒

⚠️ 易错点 1：忘记标记 visited
不标记就是死循环，这是 DFS 第一杀手。每次进入新节点第一件事就是 vis[x] = true。

⚠️ 易错点 2：回溯时忘记恢复状态
全排列、N皇后等需要枚举所有方案的问题，递归返回后必须 undo（如 used[i] = false），否则漏解。

⚠️ 易错点 3：方向数组写错
dx/dy 四个方向要配套，常见写法：{0,0,-1,1} 和 {-1,1,0,0} 对应左右上下。别搞混了。

⚠️ 易错点 4：边界检查顺序
判断越界必须在访问数组之前！写成 grid[nx][ny] 前先确认 nx、ny 在合法范围内，否则数组越界。

📘DFS递归搜索

📖概念讲解

💻代码示例

🧩互动小测

❓ 问题1：DFS遍历图时，如果不使用 visited 数组标记，最可能的结果是？

❓ 问题2：DFS递归实现本质上利用了什么数据结构？

❓ 问题3：关于回溯，以下哪项说法正确？

🏋️动手练一练

📝 编程练习：全排列

📝易错点提醒