一条路走到底，走不通就退回上一步换条路——这种"一头扎到底"的探索方式，就是 DFS。
还记得 11.3 节讲二叉树遍历时提到的前序遍历吗？"先访问自己，再一头扎进左子树的最深处，处理完了才回头处理右子树"——这种"一条路走到底，走不通（或者走完了）才往回退"的访问方式，其实有一个正式的名字，叫 DFS（Depth-First Search，深度优先搜索）。
11.3 节的 DFS 只能在"树"这种结构上走——因为树不会绕圈，每个节点最多只有两个方向（左、右孩子）可以走。但 DFS 这套思路完全可以用在更一般的场景里：走迷宫、在网格里找路、甚至是"从若干个选择里试出一条可行方案"（这是下一节"回溯"要讲的内容）。这些场景往往不止两个方向可以走，而且路径可能绕回原地——这也是本节要重点解决的新问题。
下面用一个 4×4 的小迷宫来看 DFS 具体是怎么走的。S 是起点，E 是终点，深色格子是墙，每一步都按照"右、下、左、上"的顺序尝试下一个方向：
S 出发，先往右走一步（②），发现前后左右都是墙或已经走过的格子——死胡同，只能原路退回 S；退回后换一个方向，往下走（③④⑤⑥），再往下（⑦），最后往右恰好到达终点 E（⑧）。如果把每一步的访问，看成一次函数调用（访问一个格子 = 调用一次 DFS 函数，尝试它的每个方向 = 在函数里递归调用自己），DFS 走迷宫的过程，用函数调用栈来看会更清楚——走得越深，栈里摞的层数就越多；一旦某个方向撞墙或者退无可退，这一层就从栈里弹出去，退回上一层继续尝试其它方向：
return），退回 (0,0) 这一层继续试下一个方向。右边找到终点时，栈里摞了 7 层，正好对应从起点到终点经过的 7 个格子——这也是为什么 DFS 又常被描述成"用递归的调用栈，隐式地记录了走过的完整路径"。把上面的迷宫用二维数组表示（0 表示可以走，1 表示墙），写出完整的、可以直接编译运行的程序：
| 1 | #include <iostream> |
| 2 | using namespace std; |
| 3 | |
| 4 | int maze[4][4] = |
| 5 | { |
| 6 | {0, 0, 1, 0}, // 第0行：对应演示图的第一行 |
| 7 | {0, 1, 0, 0}, |
| 8 | {0, 0, 0, 1}, |
| 9 | {1, 0, 0, 0} // 第3行，(3,3) 是终点，值是 0（可以走） |
| 10 | }; // 0 = 可以走，1 = 墙，和演示图完全对应 |
| 11 | bool visited[4][4]; // 全局数组，C++ 会自动清零（全部是 false），不用手动初始化 |
| 12 | bool found = false; // 是否已经找到终点 |
| 13 | int result = 0; // 到达终点时一共走了多少步 |
| 14 | |
| 15 | // 四个方向：右、下、左、上（和演示图的尝试顺序一致） |
| 16 | int dr[] = {0, 1, 0, -1}; |
| 17 | int dc[] = {1, 0, -1, 0}; |
| 18 | |
| 19 | void DFS(int r, int c, int steps) // steps：走到 (r,c) 已经花了几步 |
| 20 | { |
| 21 | if (r == 3 && c == 3) // 走到了终点 |
| 22 | { |
| 23 | found = true; |
| 24 | result = steps; // 当场把步数记下来，不能指望递归返回后再读 steps |
| 25 | return; |
| 26 | } |
| 27 | |
| 28 | for (int d = 0; d < 4; d++) // 依次尝试四个方向 |
| 29 | { |
| 30 | if (found) return; // 别的分支已经找到终点，不用再试了 |
| 31 | |
| 32 | int nr = r + dr[d], nc = c + dc[d]; // 下一个格子的坐标 |
| 33 | |
| 34 | if (nr < 0 || nr >= 4 || nc < 0 || nc >= 4) // 越界，跳过 |
| 35 | { continue; } |
| 36 | if (maze[nr][nc] == 1 || visited[nr][nc]) // 是墙，或者已经走过，跳过 |
| 37 | { continue; } |
| 38 | |
| 39 | visited[nr][nc] = true; // 标记这个格子走过了，出发前先标记 |
| 40 | DFS(nr, nc, steps + 1); // 递归深入这个方向，步数 +1 |
| 41 | } |
| 42 | } |
| 43 | |
| 44 | int main() |
| 45 | { |
| 46 | visited[0][0] = true; // 起点也要标记，否则可能被兜圈子走回来 |
| 47 | DFS(0, 0, 0); // 从起点 (0,0) 出发，起点自己不算一步，steps 从 0 开始 |
| 48 | |
| 49 | if (found) { cout << "找到终点！走了 " << result << " 步" << endl; } |
| 50 | else { cout << "没有路可以走到终点" << endl; } |
| 51 | return 0; |
| 52 | } |
steps 不需要像 visited 那样手动"撤销"？因为 steps 是函数参数，每一层递归调用都有自己独立的一份——递归深入的时候自然 +1 传给下一层，函数返回（回溯）的时候，这一层的 steps 就随着栈帧一起消失了，不需要手动写"steps--"。这和 11.1 节讲的"深度"是同一件事：每往下一层，深度自然加一，回退的时候也不用手动做任何清理。result 记下的步数不一定是"最短"的。DFS 只保证能找到一条能走到终点的路，不保证这条路是所有可行路径里最短的——如果把方向尝试顺序换成"下、右、左、上"，走出来的路径和步数完全可能不一样。真正能保证"最短步数"的是 BFS（还记得 11.3 节末尾提到的那个"后面章节会正式学到"的名字吗？），这也是 DFS 和 BFS 最核心的区别之一，留到"搜索进阶"模块详细展开。visited 没有手动初始化，也不会有随机的"垃圾值"？因为它是写在 main 函数外面的全局数组——C++ 规定全局变量在程序启动时会自动清零（int 全局变量默认是 0，bool 全局变量默认是 false）。但如果把 visited 挪到 main 函数内部去声明，它就变成了局部数组，局部数组不会自动清零，里面会是不确定的垃圾值，必须自己手动初始化（比如 memset(visited, false, sizeof(visited));）才能保证一开始全是 false。对比 11.3 节树上的 DFS（前序遍历），走迷宫的 DFS 多了一个必须要做的动作——标记某个格子"已经走过"（visited 数组）。这是因为树不会绕圈，从根往下走，永远不可能重新走回父节点；但迷宫（以及更一般的图）里，从一个格子出发，很可能兜一圈又走回原来的格子。如果不标记，DFS 会在几个格子之间来回打转，永远停不下来。
for 循环结束，函数自然执行到最后一行，return 回到上一层调用它的地方——这个"退回上一层"的动作就是回溯，不需要专门写额外的代码去"撤销"什么。下一节会讲一类更强调"主动撤销选择"的问题（比如排列组合），那时候回溯的动作会更明显地体现在代码里。把本节内容汇总成几条最容易踩坑的规则：
visited，或者标记的时机不对：必须在"即将递归进入某个格子之前"就标记它，而不是进入递归函数内部才标记——如果四个方向都各自在递归调用里才标记，同一个格子可能会被多个方向同时重复访问，既浪费时间，也可能导致栈溢出。上面代码选择在第 39 行、调用 DFS 之前先标记，就是为了避免这个问题。maze[nr][nc] 之前，顺序反了会导致数组越界访问。