DFS · BFS · 回溯 · 剪枝

四种基本功：DFS / BFS / 回溯 / 剪枝

一大类问题——走迷宫、解谜题、排课表、下棋——本质都是在一个巨大的状态空间里寻找一条路径或一组合法的填法。如何有条理地把可能性逐个枚举而不重不漏？核心是两种遍历方式 + 一种优化技巧：DFS（深度优先，沿一条路径走到底再回头）、BFS（广度优先，一层一层向外扩展），以及在它们之上发展出的 回溯 (backtracking) 与 剪枝 (pruning)——回溯是「选择 → 递归 → 撤销」形式的 DFS，剪枝则是「这条分支不可能产生（更好的）解，整棵子树不再展开」。每页都可以单步观察栈 / 队列的增删、格子的访问顺序、哪条路径被回溯、哪棵子树被剪。四节：DFS → BFS → 回溯 → 剪枝。

1 · DFS：沿一条路径走到底，撞墙再回头

深度优先搜索 (DFS) 的特点是沿一条路径尽可能向深处探索：从起点出发，选一个方向一直走到底，进入死胡同（没有新格子可去）才回溯到上一个还有别的岔路的位置，换个方向继续。支撑这一行为的是一个栈（后进先出，LIFO）——最新发现的格子放在栈顶、最先被取出探索，因此它总是沿「最新发现的那条线索」向深处推进。在递归写法里，这个栈就是函数调用栈。

注意两点：其一，栈顶总是「最新压入的」，所以 DFS 一旦发现新岔路就立刻进入——这就是「深度优先」。其二，当一个格子没有新邻居可压时（死胡同），下一次 pop() 自然取到更早压入的格子——这就是回溯，不需要额外编写「往回走」的代码，栈本身记录了退路。

**DFS 找到的路径不一定最短。**本例中 DFS 先沿「向下」方向进入迷宫左半边、走到死胡同再返回，最终走出一条 27 步 的路径；而真正的最短路只需 15 步（见下面 BFS：一层层向外扩，首次到达即最短）。DFS 擅长的是「找到一条路径 / 遍历所有格子」，而非「找最短」。

2 · BFS：一层层向外扩，首次到达即最短

本节与上面的 DFS 走的是同一张迷宫，对照阅读更清楚。广度优先搜索 (BFS) 按距离逐层推进：先看完离起点 1 步的所有格子，再看 2 步的，再看 3 步的……像往水里扔一颗石子，一层一层地向外扩展。支撑它的是一个队列（先进先出，FIFO）——先发现的格子先处理。正因为它严格按距离从近到远访问，所以首次到达终点时，走过的步数一定是最短的。这是 BFS 在无权图（每步代价相同）上的关键性质。

为什么首次到达即最短？BFS 按距离 ${0, 1, 2, \dots}$ 分层访问：把所有距离 d 的格子全看完，才会去看距离 d+1 的。因此终点 G 一旦从队列中取出，它的距离就不可能再被更小的值更新——这个值就是答案。关键细节：格子在入队的当下就标记 visited（而非出队时），否则同一格会被多个邻居重复加入队列、距离也会算错。

2.1 · DFS vs BFS：同一张迷宫，路径长短与访问量对比

把两种遍历方式在同一张迷宫上各跑一遍，并排看最终结果。DFS 沿一条路径深入、撞墙回溯，找到的是一条绕远的路径；BFS 逐层扩展，找到的是最短路径。代价是 BFS 为保证最短，往往要把近处的格子都访问一遍。

如何取舍：需要「最短步数」用 BFS（队列）；只需「找到一条路径 / 遍历全部 / 节省内存」或解空间很深时用 DFS（栈 / 递归）。当每步代价不再相同（边有权重）时，BFS 的「逐层扩展」就要升级为「按累计距离用优先队列扩展」——那就是 Dijkstra，再加一个启发式估计即 A*。

迷宫的「图」是现成的；当「图」需要边搜索边构造时，见下面回溯：在部分解上选择、递归、撤销。

3 · 回溯：在部分解上选择、递归、撤销

回溯本质上是在一棵决策树上做 DFS，阅读前可先看 DFS。走迷宫时「图」是现成的，但更多问题——排列、组合、数独、N 皇后——并没有一张画好的图，其「状态」是在搜索过程中逐步构造的：每一步做一个选择，把部分解向前推进一格；一旦发现这条路走不下去（或要寻找其他解），就把刚才的选择撤销、退回上一步换一个。这就是回溯 (backtracking)。它的骨架始终是三步： $选择 \to 递归 \to 撤销$ 。

用经典的 N 皇后 当例子：在 $N\times N$ 棋盘上放 N 个皇后，任意两个都不能同行、同列、同对角线互相攻击。每行恰好放一个，所以「选择」= 给当前行挑一个安全的列。挑得下就递归去放下一行；整行都没安全列，就撤回上一行的皇后、换下一列。

**掌握这三步，一大类问题即可套用。**把 safe() / record() 换掉，同一个模板能解：全排列（选一个未用过的数 → 递归 → 放回）、子集 / 组合（对每个元素做「选或不选」两个分支）、分割回文串、电话号码字母组合、数独（选一个空格填 1–9）……它们的差别只在「有哪些选择」和「什么算合法」，选择→递归→撤销 的骨架完全相同。

注意代码里的 if (!safe(row, col)) continue;——它让我们在冲突的当下就放弃整列（及其底下所有摆法），而不是放满 N 个再检查。这其实已经是一种剪枝。下面的剪枝一节会专门讨论它，并量化它节省了多少。

4 · 剪枝：这条分支不可能有解，整棵子树直接跳过

本节沿用上面回溯一节的 N 皇后例子。暴力搜索慢，是因为它把大量注定失败的分支也逐一走了一遍。剪枝 (pruning) 的思路只有一句：在树的中途就判断「这棵子树不可能有（更好的）解」，于是整棵子树直接跳过，连展开都不展开。剪得越早、越彻底，节省得越多。两类最常见的剪枝：

其一，可行性剪枝 (feasibility):当前部分解已经违反约束，再往下填也无法挽回 → 剪掉。N 皇后里「这一列和已放的皇后冲突就不必再试」就是它。

其二，最优性剪枝 (optimality / bound):当前分支即便最理想也胜不过已经找到的最好解 → 剪掉。这要先给子树估一个乐观上界，正是分支限界与 alpha-beta 的核心。

4.1 · 可视化剪枝：冲突格变红，子树不再展开

仍以 N 皇后为例。单步运行回溯，留意那些变红的格子——每一个都表示「这里放皇后会冲突，所以这一格连同它下方整棵子树（后面所有行的摆法）全部被剪掉」。剪得越早，搜索树就越小。

4.2 · 剪枝到底省了多少？（量化）

同样是找出全部解，三种走法访问的节点数天差地别（下面随棋盘 N 实时变化，注意是对数刻度的柱子）：

4.3 · 提升剪枝效果：搜索顺序很关键

剪枝的效果还与先搜索哪个分支有关。两条经验法则几乎适用于所有搜索：

其一，优先选择约束最强的变量 (most-constrained / MRV):先填「可选项最少」的那个格子（例如数独里只剩一两个候选的空格）——它最容易冲突，能尽早触发剪枝。

其二，优先尝试最有希望的取值（least-constraining / 好解优先）：先试更可能通向解 / 更优的选择，尽早得到一个较好的当前最优解，使后续最优性剪枝的阈值更高、剪掉更多分支。

再配合约束传播（填一个格子后立即收窄其他格子的候选，如数独的「唯一余数」）与记忆化（memo / 剪掉重复子问题），就构成了现代约束求解器 (CP-SAT、SAT solver) 的常规做法。

四节之间的关系：DFS 与 BFS 是两种基础遍历方式；回溯是把 DFS 用于「边搜索边构造解」；剪枝是给回溯 / 搜索加速的通用技巧。再往上，给剪枝配上「乐观上界 + 优先队列」即分支限界，博弈树上的剪枝是 alpha-beta，带权图的最短路要把 BFS 升级为 Dijkstra / A*。

5 · 实际应用

遍历与连通性:DFS / BFS 是图算法的基础——拓扑排序、求连通分量、判环、二分图染色、洪水填充（绘图工具的填充、扫雷展开）都依赖它们。

最短步数：无权图的最短路（社交网络的好友关系度数、魔方 / 华容道最少步数、迷宫寻路）用 BFS；双向 BFS、多源 BFS、0-1 BFS 是常见的加速变体。

回溯解谜：数独、N 皇后、填字、正则匹配、SQL 查询规划、编译器寄存器分配中的搜索，骨架都是回溯 + 剪枝。

剪枝决定性能：同一个搜索，剪枝的好坏可相差几个数量级——这也是分支限界、alpha-beta、约束传播 (constraint propagation) 共同的主题。