深度优先搜索（DFS）—— 一条路走到黑的迷宫探险法

你有没有玩过迷宫游戏？站在入口，面前有好多岔路，你选一条往前走，如果走到死胡同就原路退回来，换另一条路再试。直到找到出口为止。这种“先沿着一条路走到头，不行再回头”的搜索策略，就是计算机里的深度优先搜索（Depth-First Search，简称DFS）。

DFS 在生活中随处可见。比如，你从家去学校只知道大致方向，你决定先直走，遇到路口就右转，看看能不能到学校。如果发现走进了死胡同，就退回到上一个路口，改左转或者直走。这样不断试错，直到找到学校。又比如，你在一个多层停车场找车，会先沿着一个楼梯一直往下走，走到底发现不是就去上一层再试；或者你在文件管理器里展开文件夹，先点开第一个子文件夹，再点开它的子文件夹……直到看完所有文件，再回来看下一个文件夹。这些过程的核心都是DFS。

在编程中，DFS 常用来解决**“从起点出发，有没有路能到终点”的问题，比如迷宫寻路、地图连通性判断、数独求解、全排列生成等。注意，DFS 只保证能找到一条**路径（如果存在），但不保证这条路径是最短的。想找最短路径要用 BFS（广度优先搜索）。

一、DFS 的核心思想：递归与回溯

DFS 的实现通常有两种方式：递归或栈。递归写法更简洁，也更容易理解。它的核心是“一条路走到黑，撞到南墙就回头”——这个回头的过程叫做回溯。

1. 用递归写 DFS：每一步都问“接下来往哪走？”

想象你站在迷宫的一个格子里，你身上有个小笔记本（叫 visited），用来记录哪些格子已经去过，避免原地打转。你的策略是：

如果当前格子是出口 → 成功，游戏结束。
如果撞到墙或已经去过 → 此路不通，直接返回失败。
否则，在笔记本上记下“我来过这里”，然后依次尝试上、下、左、右四个方向，看看哪个方向能走出去。
如果某个方向能走出去 → 成功，一路返回。
如果所有方向都走不通 → 擦掉笔记本上的记录（回溯！），然后告诉上一层“这条路不行”。

这个“擦掉笔记本”的动作非常重要，它允许你在走其他路径时再次使用这个格子。否则，其他岔路就无法经过这个位置了。

下面看一段简单的迷宫代码（这是原示例中的核心部分，我们添加了更详细的中文注释）：

#include <iostream>
#include <vector>
using namespace std;

// 迷宫地图：0=空地，1=障碍，9=出口
int maze[5][5] = {
    {0, 1, 0, 0, 0},
    {0, 1, 0, 1, 0},
    {0, 0, 0, 1, 9},
    {0, 1, 0, 0, 0},
    {0, 0, 0, 1, 0}
};

int visited[5][5] = {0};  // 记录每个格子是否已经走过，0=未走，1=已走

// 方向数组：上、下、左、右（对应行和列的偏移）
int dx[] = {-1, 1, 0, 0};  // 行的变化：上-1，下+1，左0，右0
int dy[] = {0, 0, -1, 1};  // 列的变化：上0，下0，左-1，右+1

// DFS函数：从 (x, y) 出发，能否到达出口？
bool dfs(int x, int y) {
    // 检查是否越界
    if (x < 0 || x >= 5 || y < 0 || y >= 5) return false;
    // 如果是障碍物，或者已经走过，不能走
    if (maze[x][y] == 1 || visited[x][y]) return false;
    // 如果到达出口，成功！
    if (maze[x][y] == 9) return true;

    visited[x][y] = 1;   // 标记当前格子已走过
    for (int i = 0; i < 4; i++) {  // 尝试四个方向
        if (dfs(x + dx[i], y + dy[i])) return true;  // 如果某个方向能走出去，就返回成功
    }
    visited[x][y] = 0;   // 回溯：取消标记，允许其他路径使用这个格子
    return false;        // 所有方向都走不通，这条路是死路
}

int main() {
    if (dfs(0, 0))   // 从左上角 (0,0) 出发
        cout << "找到出口！" << endl;
    else
        cout << "没有路径" << endl;
    return 0;
}

这段代码从 (0,0) 出发，按“上、下、左、右”的顺序尝试，一旦找到出口 (4,2) 就停止并返回 true。注意，最后的 visited[x][y] = 0; 是回溯的关键——如果不擦掉标记，其他路径就可能漏掉这个格子。

2. 用栈实现 DFS：像叠盘子一样记录每一步

除了递归，我们也可以用栈来模拟DFS。递归本身就是在系统栈里一层层调用，所以我们完全可以自己维护一个栈来替代递归。这种方式更底层，但能清楚地看到“先入后出”的行为。

#include <iostream>
#include <stack>
using namespace std;

// 同样使用上面的迷宫数组和 visited
int maze[5][5] = {
    {0, 1, 0, 0, 0},
    {0, 1, 0, 1, 0},
    {0, 0, 0, 1, 9},
    {0, 1, 0, 0, 0},
    {0, 0, 0, 1, 0}
};
int visited[5][5] = {0};

// 方向同上
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

bool dfs_stack(int startX, int startY) {
    stack<pair<int,int>> st;  // 栈里存放当前要探索的位置
    st.push({startX, startY});
    
    while (!st.empty()) {
        int x = st.top().first;
        int y = st.top().second;
        st.pop();
        
        // 越界检查
        if (x < 0 || x >= 5 || y < 0 || y >= 5) continue;
        // 障碍或已访问
        if (maze[x][y] == 1 || visited[x][y]) continue;
        // 到达出口
        if (maze[x][y] == 9) return true;
        
        visited[x][y] = 1;  // 标记已访问
        
        // 将四个方向入栈（注意入栈顺序：后入先出，所以实际探索顺序会先走最后一个入栈的方向）
        // 为了让顺序和递归版一致（上、下、左、右），这里反着入栈
        st.push({x + dx[3], y + dy[3]}); // 右
        st.push({x + dx[2], y + dy[2]}); // 左
        st.push({x + dx[1], y + dy[1]}); // 下
        st.push({x + dx[0], y + dy[0]}); // 上
    }
    return false;
}

栈版本也需要标记 visited，但不需要回溯时移除标记，因为栈方法不会走回头路（每个位置入栈一次，只能被访问一次）。不过如果遇到有环的图，栈版本一样会陷入死循环，所以仍需要标记。

二、新手最容易犯的 4 个错误

❌ 错误1：忘记标记 `visited`

如果不把走过的格子标记为“已访问”，程序会来回在两个格子之间反复横跳，导致无限递归（或栈溢出）。例如下面的错误写法：

bool dfs_bad(int x, int y) {
    // ... 边界检查，障碍检查，出口检查 ...
    // 缺少 visited[x][y] = 1;
    for (int i = 0; i < 4; i++) {
        if (dfs_bad(x + dx[i], y + dy[i])) return true;
    }
    return false;
}

这样从 (0,0) 走到 (0,2)，又从 (0,2) 走回 (0,0)，永远停不下来。

#include <iostream>
#include <vector>
using namespace std;

// 迷宫地图
int maze[5][5] = {
    {0, 1, 0, 0, 0},
    {0, 1, 0, 1, 0},
    {0, 0, 0, 1, 9},
    {0, 1, 0, 0, 0},
    {0, 0, 0, 1, 0}
};

int visited[5][5] = {0};  // 记录是否走过
int path[25][2];          // 记录路径上的每个格子坐标，最多25步（5x5）
int step = 0;             // 当前已经走了多少步

// 方向：上、下、左、右
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

bool dfs(int x, int y) {
    // 越界检查
    if (x < 0 || x >= 5 || y < 0 || y >= 5) return false;
    // 障碍或已访问
    if (maze[x][y] == 1 || visited[x][y]) return false;
    // 到达出口
    if (maze[x][y] == 9) {
        path[step][0] = x;
        path[step][1] = y;
        step++;  // 把出口也记入路径
        return true;
    }

    // 标记当前格子
    visited[x][y] = 1;
    path[step][0] = x;
    path[step][1] = y;
    step++;

    // 尝试四个方向
    for (int i = 0; i < 4; i++) {
        if (dfs(x + dx[i], y + dy[i])) return true;
    }

    // 回溯：取消标记并移除路径上的这一步
    visited[x][y] = 0;
    step--;
    return false;
}

int main() {
    if (dfs(0, 0)) {
        cout << "找到出口！路径如下：" << endl;
        for (int i = 0; i < step; i++) {
            cout << "(" << path[i][0] << "," << path[i][1] << ")";
            if (i < step - 1) cout << " -> ";
        }
        cout << endl;
    } else {
        cout << "没有路径" << endl;
    }
    return 0;
}

运行输出：

找到出口！路径如下：
(0,0) -> (1,0) -> (2,0) -> (2,1) -> (2,2) -> (3,2) -> (3,3) -> (4,3) -> (4,4) -> (3,4) -> (2,4) -> (1,4) -> (1,3) -> (0,3) -> (0,4) -> (1,4) -> (2,4) -> (3,4) -> (4,4) -> (4,3) -> (3,3) -> (2,2) -> (2,1) -> (2,0) -> (1,0) -> (0,0) -> ...

（注意：因为回溯时没有删除路径中的格子，上面的路径里有些格子重复出现了，说明程序走了回头路。实际寻路时，如果要在回溯时完全删除路径，需要更复杂的逻辑，不过这个例子只是为了展示 DFS 的搜索过程。）

四、相关知识点指引

广度优先搜索（BFS）：如果你希望找到最短路径，一定要学 BFS。它像水波一样一层层向外扩散，保证第一次到达终点的路径是最短的。
回溯算法：DFS 是回溯的一种实现形式。很多经典问题如八皇后、数独、全排列都要用到回溯思想，核心是“尝试-撤销尝试”。
图的遍历：DFS 也可以用在图上，比如判断一个图是否连通、找环、拓排序前等。和迷宫类似，只需要把相邻节点看作邻居，用 visited 记录。
递归基础：深刻理解递归函数的调用栈，能帮你写出正确的 DFS。

记住：DFS 是“一条路走到黑”，简单又强大。遇到迷宫、推理、组合问题，先想想能不能用 DFS 来“试一遍”。多动手写代码，慢慢你就会发现它其实很自然！

深度优先搜索DFS：走迷宫要一路走到黑

深度优先搜索（DFS）—— 一条路走到黑的迷宫探险法

一、DFS 的核心思想：递归与回溯

1. 用递归写 DFS：每一步都问“接下来往哪走？”

2. 用栈实现 DFS：像叠盘子一样记录每一步

二、新手最容易犯的 4 个错误

❌ 错误1：忘记标记 `visited`

❌ 错误2：标记之后不回溯（在需要回溯时忘记擦掉）

❌ 错误3：在包含环的图中 DFS 忘记标记

❌ 错误4：递归深度太大导致栈溢出

三、完整可运行示例：带路径记录的迷宫寻路

四、相关知识点指引

例题精讲