DFS · BFS · 回溯 · 剪枝

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

一大类问题（走迷宫、解谜题、排课表、下棋）本质都是在一个巨大的状态空间里寻找一条路径或一组合法填法。核心是两种遍历方式加一种优化技巧：DFS 沿一条路径走到底再回头，BFS 一层一层向外扩展，回溯是「选择 → 递归 → 撤销」形式的 DFS，剪枝则在中途判定「这条分支不可能产生更好的解」而整棵子树不再展开。

1 · 深度优先搜索

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

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

图 1-1 · DFS 在迷宫上的推进过程，左侧栈的增删与格子的访问顺序同步。可单步推进观察进入死胡同后如何退回。

警示 · DFS 找到的路径不一定最短。本页这张迷宫上 DFS 先沿「向下」方向进入左半边、走到死胡同再返回，最终走出 27 步；而最短路只需 15 步（见 §2）。DFS 擅长「找到一条路径」或「遍历所有格子」，不擅长找最短。

2 · 广度优先搜索

广度优先搜索（BFS）按距离逐层推进：先看完离起点 1 步的所有格子，再看 2 步的，如此向外扩展。支撑它的是一个队列（先进先出），先发现的格子先处理。正因为严格按距离从近到远访问，首次到达终点时走过的步数一定最短——这是 BFS 在无权图（每步代价相同）上的关键性质。

图 2-1 · 与图 1-1 同一张迷宫上的 BFS。可单步推进观察队列的增删与逐层扩展的波前。

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

2.1 · 同一迷宫上的路径与访问量对比

DFS 沿一条路径深入、撞墙回溯，找到的是一条绕远的路径；BFS 逐层扩展，找到的是最短路径。代价是 BFS 为保证最短，往往要把近处的格子都访问一遍。

图 2-2 · 两种遍历在同一张迷宫上的最终结果并排：路径长度与访问格数。

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

迷宫的图是现成的；当图需要边搜索边构造时，就进入回溯。

3 · 回溯

回溯本质上是在一棵决策树上做 DFS。走迷宫时图是现成的，但排列、组合、数独、N 皇后并没有一张画好的图，它们的状态是在搜索过程中逐步构造的：每一步做一个选择，把部分解向前推进一格；一旦发现这条路走不下去，就把刚才的选择撤销、退回上一步换一个。骨架始终是选择、递归、撤销三步。

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

图 3-1 · N 皇后的回溯过程，棋盘与调用栈同步。可单步推进观察哪一行的皇后被撤回。

把 safe() 与 record() 换掉，同一个模板能解全排列（选一个未用过的数、递归、放回）、子集与组合（对每个元素做「选或不选」两个分支）、分割回文串、电话号码字母组合、数独（选一个空格填 1 至 9）。它们的差别只在「有哪些选择」和「什么算合法」，骨架完全相同。

代码里的 if (!safe(row, col)) continue; 让搜索在冲突的当下就放弃整列及其底下所有摆法，而不是放满 $N$ 个再检查。这已经是一种剪枝。

4 · 剪枝

暴力搜索慢，是因为它把大量注定失败的分支也逐一走了一遍。剪枝的思路只有一句：在树的中途就判断「这棵子树不可能有更好的解」，于是整棵子树连展开都不展开。剪得越早越彻底，节省越多。

常见的剪枝分两类。可行性剪枝看当前部分解是否已经违反约束，违反了再往下填也无法挽回，N 皇后里「这一列和已放的皇后冲突就不必再试」即是。最优性剪枝看当前分支即便最理想也胜不过已找到的最好解，这要先给子树估一个乐观上界，是分支限界与 alpha-beta 的核心。

4.1 · 冲突格与被剪掉的子树

图 4-1 · N 皇后回溯中变红的格子，每一个都表示「这里放皇后会冲突，这一格连同它下方整棵子树全部被剪掉」。可调

N

并单步推进。

4.2 · 剪枝的量化

同样是找出全部解，三种走法的搜索量差几个数量级。 $N = 8$ 时：逐格暴力枚举有 $8^8 = 16{,}777{,}216$ 个叶子；先利用「每列至多一个」按排列枚举，降到 $8! = 40{,}320$ 个叶子；而带可行性剪枝的回溯只做了 $15{,}720$ 次安全检查。 $N = 10$ 时三个数分别是 $10^{10}$ 、 $3{,}628{,}800$ 与 $348{,}150$ 。

这三个数的口径并不一致，直接比大小会读出错误结论。前两个数的是叶子（完整摆法），第三个数的是回溯树上的节点访问（每次安全检查算一次）。按这个口径， $N \le 6$ 时回溯的计数反而比按排列枚举更大： $N = 4$ 是 $60$ 对 $24$ ， $N = 6$ 是 $894$ 对 $720$ ，直到 $N = 7$ 才反超为 $3{,}584$ 对 $5{,}040$ 。这不说明小盘面上剪枝无效，只说明拿节点数比叶子数在小规模下没有意义——真正可比的是同一口径下剪枝前后的差距。

图 4-2 · 三种走法的搜索量随

N

变化，纵轴为对数刻度。可调

N

观察差距如何拉开。

4.3 · 搜索顺序对剪枝的影响

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

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

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

再配合约束传播（填一个格子后立即收窄其他格子的候选，如数独的唯一余数）与记忆化，就构成了现代约束求解器的常规做法。

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

5 · 实际应用

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

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

数独、N 皇后、填字、正则匹配、查询规划、编译器寄存器分配里的搜索，骨架都是回溯加剪枝。同一个搜索，剪枝的好坏可相差几个数量级，这也是分支限界、alpha-beta 与约束传播（constraint propagation）共同的主题。