CC++ & Algorithm

深度优先搜索（DFS）——像走迷宫一样探索

困难17
语言版本：C++Python
概述：深度优先搜索是一种沿着一条路走到黑，走不通再回头换一条路尝试的搜索方法。

深度优先搜索（DFS）——像走迷宫一样探索

你玩过走迷宫吗？当你走进一个岔路口，先选一条路一直向前，如果走进死胡同就退回到岔路口，换另一条路再试。直到找到出口，或者把所有的路都走完。深度优先搜索（DFS） 就是这种策略在计算机里的实现。

在计算机中，DFS 常用于在“图”或“树”中搜索目标、遍历所有节点，或者找出所有可能的解。比如，从一堆数字中找特定的数、解开数独、规划路径等。它依靠栈（stack）或者递归函数来记住走过的路径，确保能退回来继续探索其他分支。

核心思想：一条路走到黑，不行就回头

想象你是一个探险家，手里拿着粉笔。每到一个岔路口，先选一条没走过的路，并在路口画个标记“已走”。如果走进死胡同，就沿着粉笔印退回到上一个路口，再换另一条路。直到找到宝藏（目标）或者所有路都走完。

在代码里，DFS 就是“先深度，后广度”：优先沿着当前路径一直往下走，直到无法继续，才返回上一层，尝试其他分支。

生活中的例子：打扫房间找丢了的东西

假设你的房间里有一个玩具，你不知道它在哪个箱子或抽屉里。你决定用 DFS 的方法找它：

  1. 先打开书桌的第一个抽屉，如果里面还有小格子，就继续往深处翻（先翻最里面的小抽屉）。
  2. 如果第一个抽屉全部翻完都没找到，就退回来，打开书桌的第二个抽屉。
  3. 直到所有抽屉都翻完，或者找到了玩具。

这个过程中，你始终优先深入当前抽屉，而不是一个一个地检查所有抽屉的表面。这就是 DFS 的特点。

用递归实现 DFS——最自然的方式

递归函数就是 DFS 最常见的写法。函数自己调用自己，每次调用处理当前节点，再递归处理它的子节点。下面用一个简单的树来演示。我们把树想象成学校的组织结构：校长是根节点，下面有年级主任，再下面是各班班主任……用数组来模拟每个节点的左孩子和右孩子。

树的 DFS 遍历

#include <iostream>
using namespace std;

const int N = 10;                  // 树的最大节点数

// 左孩子数组，-1 表示没有左孩子
int leftChild[N] = {1, 3, 5, 7, -1, -1, -1, -1, -1, -1};
// 右孩子数组，-1 表示没有右孩子
int rightChild[N] = {2, 4, 6, -1, -1, -1, -1, -1, -1, -1};

// 深度优先搜索函数：从节点 node 开始遍历
void dfs(int node) {
    if (node == -1) return;        // 遇到空节点，停止递归
    cout << node << " ";           // 访问当前节点（输出它的编号）
    dfs(leftChild[node]);          // 先去左子树（一直往左走）
    dfs(rightChild[node]);         // 左子树走完，再去右子树
}

int main() {
    cout << "DFS 遍历结果: ";
    dfs(0);                        // 从根节点 0 开始
    cout << endl;
    return 0;
}

运行结果：

DFS 遍历结果: 0 1 3 7 4 2 5 6

你看，它真的“一条路走到黑”——先访问根节点0，然后一直往左：1 → 3 → 7（7的左右孩子都是-1，停止），然后回头访问7的右孩子（没有），再回到节点3，访问它的右孩子4……最后才轮到右子树2、5、6。这就像探险家先走左边最深的岔路，退回来后再走右边的路。

用栈模拟 DFS——更贴近计算机底层

递归底层就是用栈实现的。我们也可以自己写一个栈来模拟过程，这样能看清“回退”是怎么发生的。

假设还是上面的树，我们用栈手动实现 DFS：

  1. 把根节点 0 压入栈。
  2. 只要栈不为空，就弹出栈顶节点，并把它未访问的孩子（先右后左，因为栈是后进先出）压入栈，这样优先处理左孩子。

代码不展开写了，但理解递归就是理解栈的压入和弹出过程。

常见错误（新手一定要小心）

1. 忘记递归终止条件

void dfs(int node) {
    // 忘了检查 node == -1，导致无限递归直到程序崩溃
    cout << node << " ";
    dfs(leftChild[node]);
    dfs(rightChild[node]);
}

没有终止条件，递归会一直调用下去，很快栈溢出。一定要在递归函数开头判断是否应该返回。

2. 在图中忘记标记已访问节点

树没有环，所以不会走回头路。但图（比如迷宫）可能有环或重复路径。如果不标记哪个格子已经走过，DFS 就会在原地打转，永远找不到出口。

正确做法： 用一个数组 visited[] 记录每个节点是否访问过，访问前先检查。

3. 混淆递归顺序（先左后右 vs 先右后左）

改变访问左右孩子的顺序，会导致遍历的顺序不同。但 DFS 的核心依然是“优先深入”，只要先处理一个孩子到底即可。

完整示例：用 DFS 在迷宫找出口

下面是一个更贴近“走迷宫”的例子。我们用二维字符数组表示迷宫，'S'是起点，'E'是出口，'#'是墙，'.'是路。DFS 从起点开始，尝试上下左右四个方向，每走一步就在地图上标记为已走过（'X'），避免重复。

#include <iostream>
using namespace std;

const int ROWS = 5;      // 迷宫行数
const int COLS = 5;      // 迷宫列数

// 迷宫地图，'.' 是路，'#' 是墙，'S' 是起点，'E' 是出口
char maze[ROWS][COLS] = {
    {'S', '.', '#', '.', '.'},
    {'#', '.', '#', '.', '#'},
    {'.', '.', '.', '#', '.'},
    {'#', '#', '.', '.', 'E'},
    {'.', '.', '#', '.', '.'}
};

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

// 标记是否找到出口
bool found = false;

// 深度优先搜索：从 (x, y) 出发
void dfs(int x, int y) {
    // 如果越界、碰到墙、或者已经走过，就停止
    if (x < 0 || x >= ROWS || y < 0 || y >= COLS) return;
    if (maze[x][y] == '#' || maze[x][y] == 'X') return;

    // 如果到达出口，标记已找到
    if (maze[x][y] == 'E') {
        found = true;
        return;
    }

    // 标记当前格子已经走过（用 'X' 表示）
    maze[x][y] = 'X';

    // 尝试四个方向（上下左右），深入探索
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        dfs(nx, ny);
        // 如果已经找到出口，可以提前结束（但不必须）
        if (found) return;
    }

    // 如果四个方向都走不通，说明这是死胡同，可以恢复标记（可选）
    // 但这里为了简化，不恢复，保持 'X' 表示已走过
}

int main() {
    cout << "迷宫地图：" << endl;
    for (int i = 0; i < ROWS; i++) {
        for (int j = 0; j < COLS; j++) {
            cout << maze[i][j] << " ";
        }
        cout << endl;
    }

    // 找到起点位置
    int startX = -1, startY = -1;
    for (int i = 0; i < ROWS; i++) {
        for (int j = 0; j < COLS; j++) {
            if (maze[i][j] == 'S') {
                startX = i;
                startY = j;
                break;
            }
        }
    }

    cout << "\n开始用 DFS 找出口...\n";
    dfs(startX, startY);

    if (found) {
        cout << "找到出口啦！" << endl;
    } else {
        cout << "没有找到出口（迷宫无解）。" << endl;
    }
    return 0;
}

输出示例（具体路径可能因方向顺序不同而变）：

迷宫地图：
S . # . . 
# . # . # 
. . . # . 
# # . . E 
. . # . . 

开始用 DFS 找出口...
找到出口啦！

这个例子中，DFS 会从起点开始，优先向上（dx[0]=-1），如果上面是墙或边界就换方向，一直深入探索，直到找到出口或走完所有可能的路。你可以试着改变方向顺序，看看路径会如何变化。

相关指引

  • 广度优先搜索（BFS）：与 DFS 不同，BFS 像水波一样一圈一圈地扩展，适合找最短路径。
  • 回溯算法：DFS 常常是回溯算法的基础——在搜索解空间时，尝试一条路，如果不行就“回头”（撤销之前的选择），再试另一条。
  • 递归：理解递归是掌握 DFS 的关键，建议先练习写阶乘、斐波那契数列等简单递归程序。

如果你学会 DFS，解迷宫、数独、八皇后、全排列等问题都会变得有思路。记住：一条路走到黑，不行就回头——这就是 DFS 的浪漫。

例题精讲

1单选题

在使用深度优先搜索（DFS）遍历一个连通图时，以下哪种数据结构通常可以替代递归实现？

A队列
B栈
C数组
D链表
2判断题

深度优先搜索（DFS）在遍历图时，一定会找到无权图中的最短路径。

3填空题
以下代码使用DFS查找从起点(sx, sy)到终点(ex, ey)的路径，请补全递归部分（网格大小n×m，0表示空地，1表示障碍，方向按上、下、左、右）。

int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
bool visited[100][100];

bool dfs(int x, int y) {
    if (x == ex && y == ey) return true;
    visited[x][y] = true;
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx][ny] == 0 && !visited[nx][ny]) {
            if (___)
                return true;
        }
    }
    return false;
}
4单选题

对一棵有n个节点、m条边的无向图进行DFS，其时间复杂度通常为？

AO(n)
BO(m)
CO(n + m)
DO(n * m)
5填空题
下面是DFS求全排列的代码（打印1~n的所有排列），请补全递归部分。

int n;
int perm[100];
bool used[100];

void dfs(int depth) {
    if (depth == n) {
        for (int i = 0; i < n; i++) cout << perm[i] << " ";
        cout << endl;
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (!used[i]) {
            used[i] = true;
            perm[depth] = i;
            ___;
            used[i] = false;
        }
    }
}