我第一次接触 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 数独最坏情况下空白格多时会陷入非常夸张的分支爆炸。但如果改成“每次选择候选数字最少的格子去填”也就是所谓的 MRVMinimum 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 里写vectorint(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 LinksDLX算法它专门用来高效求解精确覆盖问题数独可以建模成精确覆盖用 DLX 解会更快。我自己做项目时很少会遇到需要手工写这类求解器的场景更多时候是遇到“排列组合类型的合法性校验”“角色权限路径遍历”“规则依赖闭环检测”这类 DFS 变体。如果你能把本文这套“状态-选择-撤销-剪枝”的思考方式吃透换到任何分支搜索问题上都会快很多。尤其是遇到看起来无从下手的搜索类需求不要急着套最短路径或什么高级算法先试着画一棵决策树用 DFS 和回溯搜一遍再加上合理的剪枝大概率已经能解决问题了。最后分享一个我的个人经验学 DFS 最有用的一个动作就是拿着纸笔把一个 3×3 数独或一个 N4 的皇后棋盘手动展开成决策树然后在代码里逐步打印递归进入和返回的位置亲眼看到每个分支的深入与回退。那一眼看明白的感觉比看二十篇教程都管用。