企业官网建设流程全解析

我第一次接触 DFS（深度优先搜索）是在做“全排列”这道题的时候。当时看到别人的解答只有短短十来行递归代码，我却完全看不懂为什么能输出所有排列。后来弄明白了，DFS 和回溯搜索并不是什么高深概念，它就是一个“走迷宫”的思路：一路走到黑，撞墙了就退一步换条路再走。

后来刷题、写业务系统，发现 DFS 几乎是算法面试和工程排查里出现频率最高的基础算法之一。搭一个权限路由、做一个排班校验、分析一幅图像的连通区域、甚至写个数独求解器，底层都可能是 DFS。这也是为什么我强烈建议每个开发者都把它吃透：很多看起来花哨的算法，本质都是在 DFS 的骨架上加了剪枝、记忆化或者启发式策略。这篇文章我就按自己做题和做项目时的理解，从思想、模板、剪枝一直讲到图和网格上的应用，最后带一个完整的数独求解器实战，尽量把 DFS 这件事讲到能直接上手用，而不是停留在会背代码。

1. DFS 到底是什么：先走到黑的贪心式搜索

1.1 从迷宫说起

想象你走进一个岔路很多的迷宫。策略有两种：一种是不管前方还有多少岔路，认准一条道一直往前走，走不通就退到最近的岔路口换一条；另一种是像波纹一样从入口一层一层往外推进，先探完所有一步能到的格子，再探两步能到的。

第一种就是深度优先搜索，第二种是广度优先搜索（BFS）。

DFS 的关键动作有两个：深入和回退。深入指的是沿着当前选择不断往前试探；回退指的是当探测到终点、死路，或者发现当前路径已经不满足条件时，退回上一层重新选择。

这个“退回上一层重新选择”的动作，就是“回溯搜索”这个名字的来源。看一个最简单的迷宫路径问题：从 (0,0) 走到 (n-1,m-1)，矩阵里 1 是墙，0 是路。用 DFS 写就是：

def dfs(grid, x, y, path): # 剪枝：越界、撞墙、已访问 if not (0 <= x < len(grid) and 0 <= y < len(grid[0])): return False if grid[x][y] == 1 or grid[x][y] == '#': return False if (x, y) == target: return True path.append((x, y)) grid[x][y] = '#' for dx, dy in dirs: nx, ny = x + dx, y + dy if dfs(grid, nx, ny, path): return True path.pop() grid[x][y] = 0 return False

这段代码里体现了 DFS 的全部核心：先判断当前状态有没有希望，有希望就往下一层试探，试探失败就撤销刚才的修改，回到上一层继续试别的方向。很多人刚看这段会困惑“为什么要 grid[x][y] = '#'，又为什么要改回 0”，这就是后面要讲的恢复现场，先记住这两个动作。

1.2 递归与栈：为什么递归天然就是 DFS

有些朋友会问：DFS 是不是一定要用递归？其实不是，DFS 的本质是维护一个“待回溯路径”，而这个路径天然符合栈的先进后出结构。递归不过是借用了函数调用栈来维护它，所以写起来最自然。如果我们不用递归，可以用显式栈手动模拟：

if path: last = path.pop() # 回退

这段代码放在显式栈版本里，作用就等效于递归里的函数返回。我在公司带新人时经常打这个比方：递归就是“单位层层上报，最后由最底层员工返回结果”，显式栈就是“把审批单一张张压在桌上，办完了一个一个翻出来撤单”。

显式栈的好处是不会爆调用栈，坏处是代码更啰嗦，需要手动记录每一步的状态。递归的好处是代码即状态，函数参数天然保存了当前路径所有信息，坏处是递归深度太深会栈溢出，后面我会专门讲怎么处理。

2. 回溯搜索的核心模板：状态、选择、撤销

2.1 模板代码与心法

回溯搜索是 DFS 的一种典型应用场景，它把问题建模成“在多阶段决策中搜索所有可行解”。做题多了你会发现，回溯搜索的代码结构几乎固定：

def backtrack(路径, 选择列表): if 满足结束条件: 记录结果 return for 选择 in 选择列表: 做选择 # 把当前选择加入路径，并更新状态 backtrack(路径, 新的选择列表) 撤销选择 # 把状态恢复到选择之前

这个模板有三大要素：

• 状态：当前在决策树的哪个节点，已经选了什么。
• 选择列表：当前状态下还能选哪些选项。
• 结束条件：到达叶子节点，或者路径已经不合法。

为什么必须撤销选择？因为状态是一路共享的。如果递归到最深一层回来时，不把数组里刚填的数字清掉，下一次循环选别的数字时，数组里就残留了上一轮的污染数据，最后得到的结果全是错的。

我见过不少人套模板时傻傻地抄“撤销”，却不知道为什么撤销。这里说透：回溯的本质是深度优先地遍历决策树，所谓“状态”就是从根到当前节点的路径上的累积变更。每次递归返回上层，相当于把这层做的修改全部回滚，让兄弟分支从相同起点开始。

2.2 全排列与组合去重

全排列是最经典的回放入门题。给定一个不含重复数字的数组，返回所有可能的排列。代码：

def permute(nums): res = [] n = len(nums) used = [False] * n path = [] def dfs(): if len(path) == n: res.append(path[:]) # 深拷贝 return for i in range(n): if used[i]: continue used[i] = True path.append(nums[i]) dfs() path.pop() used[i] = False dfs() return res

注意res.append(path[:])这行。如果不写[:]而直接 append(path)，到后面 path 被不断 pop 和修改，res 里存的其实是同一个数组对象的引用，最后所有结果都会变成空的或者同一个排列。这是新手最容易踩的坑，我每年都看到有人在这里卡半天。

组合和排列的区别在于组合不关心顺序。比如从 [1,2,3] 中选 2 个数，(1,2) 和 (2,1) 算同一种，所以需要加一个start参数，强制下一次只能从当前索引之后选：

def combine(n: int, k: int): res = [] def dfs(start, path): if len(path) == k: res.append(path[:]) return for i in range(start, n + 1): path.append(i) dfs(i + 1, path) path.pop() dfs(1, []) return res

排列用used数组避免重复使用同一个元素，组合用start索引避免选择顺序不同的重复集合，这个对比记牢，遇到“去重”题目就不会乱了。

2.3 N 皇后问题的完整解法

N 皇后是一道非常经典的回溯搜索题，也很能检验对状态的把握是否扎实。问题是在 N×N 棋盘上放 N 个皇后，要求任意两个皇后不能在同一行、同一列、同一条对角线上。因为每行只能放一个皇后，所以可以用一个长度为 N 的数组cols表示每一行的皇后放在第几列，这样天然避开了“不同行”这个约束，只需要检查列冲突和对角线冲突：

def solveNQueens(n): res = [] cols = [-1] * n # cols[行] = 列 def is_valid(row, col): for r in range(row): c = cols[r] if c == col or abs(c - col) == row - r: return False return True def dfs(row): if row == n: res.append(build_board(cols)) return for col in range(n): if is_valid(row, col): cols[row] = col dfs(row + 1) cols[row] = -1 dfs(0) return res

对角线冲突的判断是abs(c - col) == row - r，意思是两个格子的行差等于列差时，它们在同一条斜线上。每次进入下一行前，不用跟之前所有皇后逐格对比，只需要跟已有的每个皇后做一次差分判断即可，时间复杂度 O(N) 的一维判断，写起来很舒服。

N 皇后最典型的剪枝是：只搜索一半列的对称位置。因为第一行的皇后放在第 0 列和放在第 N-1 列，得到的解是对称的，算一遍就能复制到另一边，这能让时间直接少一半。这类由问题结构引入的剪枝，就是下一节主角。

3. 剪枝：决定回溯算法实战价值的分水岭

3.1 三类常见剪枝思路

裸 DFS 的复杂度往往是指数级甚至阶乘级，真正决定它能否落地的，是剪枝做得好不好。我按自己的使用习惯把剪枝分为三类。

第一：可行性剪枝（约束剪枝）

走某条分支前提前判断这条路是否已经不可能到达答案。比如数独填格子时，某个候选数已经在同一行、同一列或同一宫里出现，就直接跳过；N 皇后里判断当前位置会不会攻击已有皇后，也是可行性剪枝。这类剪枝是回溯搜索默认必须做的。

第二：最优性剪枝（边界剪枝）

主要用于搜索最优解的问题。比如 0-1 背包问题里，如果当前已经装下的价值加上剩余物品最大可能价值都小于当前已知最优解，就提前 return，不再深入搜索。这类剪枝依赖一个“乐观估计函数”，估计值越紧，剪枝越狠。

第三：对称性剪枝与启发式顺序优化

从问题的结构特性入手。比如 N 皇后第一行只搜一半列；比如全排列中对相同元素先排序，并在递归中跳过重复值；比如搜索“从某个状态到达目标”的最短步数时，可以结合一个启发式函数评估剩余需要几步，能走到更远处再优先搜。

3.2 结合例题看剪枝效果

数独求解器是最能体现剪枝价值的例子。先按最普通的 DFS 填法：从左到右、从上到下依次找空格，每个空格从 1 试到 9。对于标准 9×9 数独，最坏情况下空白格多时，会陷入非常夸张的分支爆炸。

但如果改成“每次选择候选数字最少的格子去填”，也就是所谓的 MRV（Minimum Remaining Values）启发式，效果会有天壤之别。这个思路本质是优化搜索顺序：把可能性最少的分支放在最上层，一旦这条路不行，很快就能发现并回溯；如果这条路行，也会因为后面的空格越来越少而飞快收敛。

我给你一个量级感觉：用“顺序填”的方式解一个中等偏难的空数独，可能在几秒到几十秒；但用 MRV 策略，同一台机器上往往几十毫秒内出结果。这个差距不是几倍，而是几百上千倍的差距，而这仅仅是因为我们改变了搜索顺序，这就是剪枝的魅力。

补充一个很实用的切入口：回溯搜索里可以优先考虑“失败风险最高的分支”，和排期决策里的“最紧任务先排”是一个道理。工程里要解决资源分配问题时，这个思路同样成立。

4. DFS 在图上和网格上的身影：不再只是回溯

DFS 不止用于回溯搜索，它本身是图遍历的基本方法，很多看似和图没关系的场景，本质上也能被建模成图。

4.1 网格连通块问题

有一类很常见的面试题：给一个 01 矩阵，1 代表陆地，0 代表水，求陆地连通块的数量。每个格子上下左右相邻，连通算同一块。解决思路就是从每个没访问过的陆地出发做 DFS，把整块陆地都标记成已访问，计数器加一。伪代码：

def num_islands(grid): count = 0 for i in range(len(grid)): for j in range(len(grid[0])): if grid[i][j] == '1': count += 1 infect(grid, i, j) return count def infect(grid, i, j): if not (0 <= i < len(grid) and 0 <= j < len(grid[0])): return if grid[i][j] != '1': return grid[i][j] = '2' infect(grid, i + 1, j) infect(grid, i - 1, j) infect(grid, i, j + 1) infect(grid, i, j - 1)

这个写法很多人叫“感染函数”，因为像病毒扩散一样，DFS 把相邻陆地全部染色。注意这里我把访问标记直接修改在原来的grid上，避免开额外 visited 数组。如果你的业务场景不允许改输入数据，就要用一个visited二维数组，道理是一样的。

写这类题最关键的一点：递归调用前必须确保当前格子确实需要继续搜索，否则会无意义地调用四次，导致重复遍历甚至死循环。

4.2 拓扑排序与环检测

在工程里解析依赖关系时，经常需要判断依赖图有没有环，并按依赖顺序执行任务。DFS 可以顺便完成拓扑排序，经典方法是“三色标记法”：每个节点有三种状态，未访问（白色）、正在访问（灰色）、访问完成（黑色）。伪代码：

state = [0] * n # 0 白，1 灰，2 黑 def dfs(u): state[u] = 1 for v in graph[u]: if state[v] == 1: raise CycleError() if state[v] == 0: dfs(v) state[u] = 2 order.append(u) # 这里是逆后序，倒转即拓扑序

当我们在 DFS 过程中遇到一个灰色节点，说明从当前节点有一条回到它自己的路径，图中存在环。所有节点都变黑后，把order倒转，得到的序列就是一个合法的拓扑顺序。

我记得以前处理一个模块加载器时，就用这种思路在启动前做依赖环校验，代码只有几十行，却比当时团队手写的两处循环依赖检查更可靠，也更省内存。

4.3 记忆化搜索：DFS 和动态规划的交汇点

DFS 虽然会深度搜索所有路径，但很多搜索过程中会反复计算相同子问题。如果我们在 DFS 返回值时顺手保存一份结果，下次遇到相同状态直接查表返回，这就是记忆化搜索，本质上就是带缓存的 DFS。

拿最基础的“爬楼梯”举例：按 DFS 写法求解第 n 阶走法，会瞬间指数爆炸，因为中间状态会被重复计算。加上一个memo数组缓存后，每个状态只计算一次：

memo = {} def climb(n): if n <= 2: return n if n in memo: return memo[n] memo[n] = climb(n - 1) + climb(n - 2) return memo[n]

记忆化搜索和动态规划是等价的。区别只在于动态规划通常从底往上递推，而记忆化搜索从顶往下递归。面试如果被问到“DFS 和 DP 的区别”，你可以从这个角度切入。很多大佬喜欢先写 DFS，再加 memo，再改成 DP，三步过渡，思路会非常清晰。

5. 实战中我踩过的坑，希望你一次都别踩

5.1 递归深度与栈溢出

DFS 写递归确实爽，但 Python 默认递归深度限制一般只有 1000 层，遇到链路很深的递归题直接 RecursionError。我在跑一个带环检测的依赖遍历时，就因为这个被线上日志打了一脸。常规解决办法有几种：

• 调用sys.setrecursionlimit(5000)提高限制，适合深度可评估的场景；
• 改成显式栈迭代版本，从根上避免调用栈限制；
• 把深层 DFS 改成 BFS，如果问题允许。

这里提醒一句：setrecursionlimit并不是无限调高就安全。Python 每层递归都会占一部分 C 栈内存，调太高可能导致进程崩溃，尤其是内存受限的容器环境。我的习惯是评估最大深度后设置一个略有余量的值，绝不超过系统实际承受能力。

5.2 忘记恢复现场

我见过最典型的 bug：某新人写子集问题时，递归内部 path 一直在 append，但忘了在递归返回后 pop，最后结果里所有分支共享同一个被塞满的 path。这类问题很容易被忽略，因为有时候“不恢复现场”程序也能跑出部分正确答案，但数据一变就全崩。

判断是否需要恢复现场的简单方法：看你在递归前是否修改了“沿途共享”的状态变量。如果每个分支前都把参数值原样传入下一层，不修改共享变量，那就不需要恢复；如果复用了同一个列表、字典、数组，就需要在递归结束后把改动还原。恢复现场要跑在递归调用之后、下一次循环选择之前，顺序错了照样出问题。

5.3 可变对象的引用陷阱

这个坑在结果保存阶段尤其常见。写res.append(path)而不是res.append(path[:])，是所有回溯算法初学者最容易掉进去的坑。因为 path 是一个可变列表，递归结束后它会回到空状态，但 res 里存的引用还是那同一个列表。最后打印 res，看到的都是同一个空列表或同一个最终状态。

解决方式就一句话：保存结果时始终使用深拷贝。Python 里写path[:]或list(path)，Java 里写new ArrayList<>(path)，C++ 里写vector<int>(path)。别省这一步。

5.4 访问边界判断与坐标顺序

在网格类 DFS 里，经常要写if grid[nx][ny] == '1' and 0 <= nx < m and 0 <= ny < n，注意边界判断和值判断顺序不能颠倒。如果先访问grid[nx][ny]，而nx已经越界，就会直接抛异常。正确的姿势是先把边界条件显式写完整，再取值判断。

另外，四个方向的顺序有时候会影响搜索路径。比如在“输出所有路径”的场景下，方向顺序会决定输出序列的顺序。如果面试官要求字典序答案，那你把方向数组按坐标字典序排序就行。

5.5 重复状态与缓存失效

有时候我们想加点 memo 优化，却发现结果不对。一个典型原因是没有把“已走过的路径”纳入状态。比如求从起点到终点的所有路径时，单纯用(x, y)作为缓存键是错误的，因为到同一个格子的路径不同，后续能走的分支也不同。只有当你关心“能否到达”或“最短步数”这类最优化问题时，才适合用坐标作为键。用缓存前先问自己：当前状态的所有信息都体现在这个键里了吗？如果答案是否定的，就别缓存。

6. 完整实战：用 DFS 解数独

6.1 问题建模与状态选择

数独可以看成一个 9×9 的回溯搜索问题，目标是把所有空格填成合法数字，让每行、每列、每个 3×3 宫都包含 1-9 各一次。

状态非常明确：当前棋盘上每个格子填了什么。选择列表就是每个空格可选的数字集合。结束条件是棋盘填满。DFS 的每一层就是在处理一个空格。

但因为空格可能很多，直接盲目遍历所有空格很容易超时。用前面讲到的 MRV 思想，每次从所有空格里挑一个“候选数字最少”的格子来填，搜索效率会大幅提升。我在 LeetCode 上测试，标准数独题用 MRV 版本基本都能毫秒级通过。

6.2 剪枝与编码实现

先维护三个集合数组：rows[i] 表示第 i 行已有的数字集合，cols[j] 表示第 j 列已有的数字集合，boxes[k] 表示第 k 个宫已有的数字集合。每次填数时检查这三个集合，填完后同步更新三个集合，回溯时同步回滚。完整代码：

def solveSudoku(board): rows = [set() for _ in range(9)] cols = [set() for _ in range(9)] boxes = [set() for _ in range(9)] for i in range(9): for j in range(9): if board[i][j] != '.': v = board[i][j] rows[i].add(v) cols[j].add(v) boxes[i // 3 * 3 + j // 3].add(v) def find_next(): best_i = best_j = -1 best_options = [] for i in range(9): for j in range(9): if board[i][j] == '.': box = i // 3 * 3 + j // 3 options = [ v for v in "123456789" if v not in rows[i] and v not in cols[j] and v not in boxes[box] ] if not options: return -1, -1, [] if not best_options or len(options) < len(best_options): best_options = options best_i, best_j = i, j if len(options) == 1: return best_i, best_j, best_options return best_i, best_j, best_options def dfs(): i, j, options = find_next() if i == -1: return True if options == []: return False box = i // 3 * 3 + j // 3 for v in options: board[i][j] = v rows[i].add(v) cols[j].add(v) boxes[box].add(v) if dfs(): return True rows[i].remove(v) cols[j].remove(v) boxes[box].remove(v) board[i][j] = '.' return False dfs()

代码里find_next每次动态找最优空格，虽然是 O(81) 的扫描，但换来的搜索树规模下降远大于这个成本。如果想进一步优化，可以针对每个空格的候选数字维护一个候选集合，并用堆排序实时取最小，不过对于 9×9 数独来说，上面的版本已经非常够用。

6.3 实测与扩展想法

我把这个求解器拿几个知名困难数独案例试过，从 LeetCode 的 hard 到一些网站标称“世界最难数独”，基本都是毫秒级出结果。相比最朴素的“顺序空白格回溯法”，MRV 的加速效果非常明显，这也验证了前面讲的“剪枝顺序优化才是回溯算法的灵魂”。

如果对性能有更强诉求，可以继续往两个方向深挖：一是用位运算压缩候选集合，把一个格子的候选数字从数组变成一个 bitmask，用位运算快速取交集，速度还能再上一个台阶；二是了解 Dancing Links（DLX）算法，它专门用来高效求解精确覆盖问题，数独可以建模成精确覆盖，用 DLX 解会更快。

我自己做项目时很少会遇到需要手工写这类求解器的场景，更多时候是遇到“排列组合类型的合法性校验”“角色权限路径遍历”“规则依赖闭环检测”这类 DFS 变体。如果你能把本文这套“状态-选择-撤销-剪枝”的思考方式吃透，换到任何分支搜索问题上都会快很多。尤其是遇到看起来无从下手的搜索类需求，不要急着套最短路径或什么高级算法，先试着画一棵决策树，用 DFS 和回溯搜一遍，再加上合理的剪枝，大概率已经能解决问题了。

最后分享一个我的个人经验：学 DFS 最有用的一个动作，就是拿着纸笔把一个 3×3 数独或一个 N=4 的皇后棋盘手动展开成决策树，然后在代码里逐步打印递归进入和返回的位置，亲眼看到每个分支的深入与回退。那一眼看明白的感觉，比看二十篇教程都管用。