一说“搜索之 DFS”很多人第一反应是刷题网站上的“深度优先搜索”脑子里立刻浮现出递归、回溯、二叉树、全排列那套东西。但把搜索这个词往外稍微拉一拉你会发现 DFS 其实是整个算法体系里最贴近“人本能”的一种搜索方式——人走进一个分岔路口凭直觉往一条路走到头走不通再退回来换一条这不就是深度优先吗所以这篇博文我不想只重复教科书里的定义而是想从“为什么 DFS 靠谱”“怎么写才能不出错”“哪些场景真能派上用场”三个角度把这条经典搜索路径彻底讲透。适合看这篇内容的人我大概分三类一是刚开始刷算法题、对递归和搜索树还比较懵的初学者二是工作中需要处理遍历、求解、排列类问题的开发者想系统梳理一下 DFS 的完整写法和坑点三是准备面试、希望用最短时间把 DFS 相关的常考题型抓牢的朋友。我下面讲的所有内容都会围绕“搜索之 DFS”这个核心展开把思路、代码、调试经验一次说清楚。1. 搜索之 DFS先弄懂它在搜什么1.1 深度优先到底是什么深度优先搜索Depth-First Search简称 DFS的核心行为可以用一句话概括从起点出发沿着一条路径尽可能走到尽头走不通就退回上一个岔路口再换下一条路径继续尝试。这句话里藏着两个关键动作一个是“深入”一个是“回溯”。深入指的是顺着某条分支一层层往下走每走一步就把当前状态压入一个隐式的搜索栈回溯则是当当前分支无法继续要么到底了要么不符合要求时撤销当前状态回到上一层尝试其他未被访问过的分支。生活化的例子特别多。比如你在一栋陌生的办公楼里找一间会议室进了走廊后先往左边走左走到头发现是安全通道退回来再走中间的走廊中间走到一半看到分叉先试左分叉又到头了退回来走右分叉……这一整套行为就是 DFS。如果反过来的话你会先把每一层的所有房间都快速扫一遍再往下一层去那就是宽度优先搜索BFS的思路了。既然是“搜索之 DFS”搜索目标不只是“找到某个节点”还可能是找路径、找可行解、找最优解前置的枚举集合。比如迷宫问题目标是走到出口排列问题目标是生成所有排列连通性问题目标是找出所有连成一片的格子。DFS 在不同场景里只是“状态定义”不同底层机制是完全一致的。1.2 为什么 DFS 是搜索问题的第一选择你可能会问能搜索的算法那么多为什么 DFS 地位这么高最直接的原因是实现简单、思路直观。一个递归函数加几个参数就能完成一次完整的状态空间遍历。相比之下BFS 需要维护队列、记录层数代码量明显更大而更高级的搜索优化比如双向 BFS、启发式搜索A*、IDA* 等很多时候也是在 DFS/BFS 骨架上做文章。其次DFS 天然贴合“试探-回溯”的求解模式。很多问题并不是单纯找一条路而是需要尝试所有可能性再判断哪个方案合法。比如八皇后问题、数独求解、组合拆分这类问题的本质是“在状态树上枚举”DFS 是唯一一个用最少代码量就能完整覆盖整棵状态树的算法。还有一点DFS 的空间效率在深度优先进行时表现优异。树或图的搜索过程中DFS 只需要存储当前路径上的节点也就是栈的深度而 BFS 需要存储一整层的节点。在最坏情况下如果搜索树很深但相对窄DFS 的空间消耗会远小于 BFS。当然这不是绝对的深到会让栈溢出时也要注意这点我在后面章节专门讲。所以在大多数“求所有解”或“判断是否存在解”的场景里DFS 永远是第一个被想到的方案。它未必是最快的但一定是最不容易写错、最方便调试的那个。2. DFS 的核心机制与避坑清单2.1 递归的本质系统栈在背后做了什么写 DFS 最常见的姿势就是递归。递归之所以能实现“深入再回溯”依赖的是函数调用时系统自动维护的调用栈。每次调用递归函数系统会把当前函数的局部变量、参数、返回地址压入栈中函数返回时栈帧弹出恢复到调用前的状态。从抽象层面看这个栈帧就是“当前搜索路径上的状态”。递归的好处是你不需要自己管理状态的回退每次调用从函数返回状态自然恢复到上一层的值。看一个最简单的二叉树前序遍历def dfs_preorder(node): if node is None: return visit(node) # 访问当前节点 dfs_preorder(node.left) # 深入左子树 dfs_preorder(node.right) # 深入右子树函数先访问当前节点然后朝左子树一头扎进去左子树全部走完再回到当前节点继续右子树。这个“回到当前节点”的动作靠的就是左子树调用结束后栈帧自动弹栈、变量值恢复。但递归并不总是完美的。有两个隐患需要提。一是当搜索深度过大时系统栈被撑爆程序直接崩溃Python 里最常见的报错是 RecursionError。二是递归函数里如果对状态变量做了修改忘记在返回前撤销回溯那么后续分支访问到的就是被污染的状态结果出错。2.2 递归爆炸风险与手写栈方案系统栈的空间并不是无限的默认情况下Python 的递归深度限制通常是 1000 层左右。如果搜索空间本身相当深比如在处理某些树形结构、迷宫网格时一探到底递归版 DFS 会直接触发 RecursionError。此时有两个处理方向。第一个方向是调整递归深度限制import sys sys.setrecursionlimit(100000)这个办法能让一部分场景继续跑下去但治标不治本。如果深度特别大还是会崩而且过深递归在性能上也存在风险。第二个方向是手写栈模拟递归这是推荐掌握的技术。用显式的列表栈存储待访问的状态替代函数调用栈。迷宫逃出问题的迭代版写法就是这样def dfs_maze_iterative(maze, start, target): stack [start] visited set() visited.add(start) directions [(0, 1), (1, 0), (0, -1), (-1, 0)] while stack: x, y stack.pop() if (x, y) target: return True for dx, dy in directions: nx, ny x dx, y dy if 0 nx len(maze) and 0 ny len(maze[0]) and (nx, ny) not in visited and maze[nx][ny] ! #: visited.add((nx, ny)) stack.append((nx, ny)) return False这套写法不受递归深度限制而且状态管理完全看得见摸得着。唯一要注意的是迭代版的“访问顺序”和递归版存在细微差异但搜索结果不受影响因为目标是把状态空间走完。2.3 剪枝让搜索量急剧下降的要害DFS 的朴素逻辑是所有分支全部遍历复杂度通常是指数级。真正让 DFS 从“理论上能搜”变成“实际能用”的关键就是剪枝。所谓剪枝就是在搜索过程中提前判断某条分支已无希望直接跳过不继续深入。剪枝的时机有三类合法性剪枝当前状态已经违反约束条件立即停止。边界剪枝网格搜索中越界的位置直接返回。最优性剪枝已经找到过一组解而当前路径长度已经超过历史最优就没必要继续走了。最典型的一个例子是 N 皇后问题。每一层放一个皇后但如果新放的位置会和之前的皇后互相攻击就不用继续往下一层递归了直接回溯。这个剪枝能把穷举所有摆法的巨大搜索量压缩到非常小的规模。代码里体现剪枝的一般范式是这样def dfs_nqueens(row, n, cols, diag1, diag2, result): if row n: result.append(cols[:]) return for col in range(n): if col in cols or (row - col) in diag1 or (row col) in diag2: continue # 剪枝 cols.append(col) diag1.add(row - col) diag2.add(row col) dfs_nqueens(row 1, n, cols, diag1, diag2, result) cols.pop() diag1.remove(row - col) diag2.remove(row col)剪枝的作用放在面试和实际工程里都是“能把一小时的超时变成毫秒级返回”的立竿见影手段。很多人觉得 DFS 慢其实是没剪枝或者剪枝条件放得太靠后。3. 两种最常用的 DFS 写法与调试技巧3.1 递归实现以迷宫逃出为例迷宫问题是搜索之 DFS 最容易理解的载体。这里说一个带状态标记的完整实现。假设迷宫用二维数组表示0代表可走1代表墙起点是(0,0)目标是(m-1, n-1)。def dfs_maze_recursive(maze, x, y, target_x, target_y, visited): if not (0 x len(maze) and 0 y len(maze[0])): return False if maze[x][y] 1 or (x, y) in visited: return False if x target_x and y target_y: return True visited.add((x, y)) for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]: if dfs_maze_recursive(maze, x dx, y dy, target_x, target_y, visited): return True return False这里有几个细节值得注意。第一visited集合非常关键它保证同一个格子不会被反复探索否则在网格里会来回打转形成死循环。第二边界检查要放在迷宫值检查之前否则索引会越界报错。第三返回的时机要谨慎找到目标就应该立刻一层层返回 True而不是继续搜索其他分支。写递归 DFS 的时候我建议把“当前层只管当前层的事”当成原则。这句话的意思是当前这层递归只负责判断当前位置是否合法、是否到达目标、然后向四个方向发起调用至于深层的结果如何处理不属于当前调用的职责。一旦想混在一起代码就很容易出错。3.2 迭代实现手写栈解决爆栈迷宫逃出的迭代版本在前面已经给出过这里重点讲一下递归和迭代在写法上的对应关系。递归版的逻辑是当前状态放在函数参数里调用子任务时子任务的状态通过参数传递子任务结束返回本层继续处理剩余方向。迭代版则是把待处理状态放进栈里每次弹出一个状态处理它再把新状态压入栈中。两者的区别在于递归的栈帧由系统管理迭代的栈由我们自己管理。所以迭代版要额外维护的信息是“当前处理到哪个方向了”。如果只是简单地把下一个位置压栈不需要记录方向上面代码就能满足。但如果你要 DFS 输出一条完整路径而不是单纯判断可达性就需要把“路径上下文”一并压入栈。def dfs_maze_path(maze, start, target): stack [(start, [start])] # (当前位置, 已走路径) visited {start} while stack: (x, y), path stack.pop() if (x, y) target: return path for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]: nx, ny x dx, y dy if 0 nx len(maze) and 0 ny len(maze[0]) and (nx, ny) not in visited and maze[nx][ny] ! 1: visited.add((nx, ny)) stack.append(((nx, ny), path [(nx, ny)])) return None这里把路径随状态一起存储虽然会占用一定内存但在深度不大时比回溯维护的方式更容易理解。如果谜宫格子数量很大更省内存的方案是每个状态记录“上一个状态”最后再反向还原路径。这套做法在竞赛里很常见面试中如果被追问也是加分项。3.3 边界条件与常见错误速查DFS 不出错的关键在于把边界条件和状态还原理顺。我把实际踩过的坑整理成了下面这个速查表发布到社区以后反响一直不错问题症状解决办法忘记标记已访问无限递归、死循环入栈/进入递归前先加入 visited边界越界IndexError先检查坐标范围再做其他判断未回溯状态后续分支结果错误在递归返回前撤销对共享状态的修改访问了错误的起点/终点结果一直错明确起点终点坐标测试单个格子用例递归深度过大RecursionError手写栈替代递归或调大递归限制剪枝条件过宽松搜索超时把最严格的约束放在最外层判断重复目标被反复入栈内存膨胀入栈前检查目标是否已在 visited这个表里的每一项我几乎都在实际写题和工作里遇到过。尤其是“未回溯状态”和“忘记标记已访问”两个问题占比最高。4. 三个高频场景全排列、连通块、搜索二叉树4.1 全排列问题DFS 与回溯的结合全排列是 DFS 的经典入门题也是面试出现频率极高的问题。求一个数组的所有排列本质上就是遍历一棵排列树第一位选哪个数字第二位选哪个数字以此类推。def permute(nums): result [] used [False] * len(nums) def dfs(path): if len(path) len(nums): result.append(path[:]) return for i in range(len(nums)): if used[i]: continue used[i] True path.append(nums[i]) dfs(path) path.pop() used[i] False dfs([]) return result这段代码最核心的是path.pop()和used[i] False这两行。没有这两行前面选过的数字就永远留在状态里后续分支都会被错误地“锁定”。很多新手第一次写全排列结果莫名其妙缺少很多排列基本就是回溯这一步漏了。我在讲 DFS 回溯时喜欢用一个比喻递归往下走是出门探索回溯就是把出门带的东西原样放回原位确保下一次出门时家里和出门前一样。排列的去重也是容易出错的点。如果 nums 里含有重复数字需要在排序后加一个条件如果当前数字和前一个数字相同且前一个数字没被用过跳过。这个写法初看比较绕实际记住一句话就行重复数字只能从前往后依次使用。4.2 连通块问题网格型 DFS连通块问题把 DFS 从“找路径”扩展到了“找区域”。典型场景包括岛屿数量、被围绕的区域、图像处理里的区域填充等。核心是在一个二维网格里从某个点出发把所有相连的同类格子全部标记一遍。def num_islands(grid): if not grid: return 0 rows, cols len(grid), len(grid[0]) visited [[False] * cols for _ in range(rows)] count 0 def dfs(x, y): if not (0 x rows and 0 y cols): return if grid[x][y] 0 or visited[x][y]: return visited[x][y] True dfs(x 1, y) dfs(x - 1, y) dfs(x, y 1) dfs(x, y - 1) for i in range(rows): for j in range(cols): if grid[i][j] 1 and not visited[i][j]: count 1 dfs(i, j) return count这段代码里有一个隐藏得很深的问题让我在真正写这类题目时栽过跟头递归调用四个方向的顺序不影响正确性但极端情况下会影响 dfs 函数的栈深度。如果你总是先走上、再走右、再走下、再走左在一条很长的竖向网格里递归深度会被拉满如果先走上下再走左右类似情况也可能发生。所以当网格特别大时为了稳定性建议直接改成手写栈版本。还有一个空间优化技巧直接修改原始 grid 把访问过的陆地标记成0可以省掉 visited 数组。但这种做法会改变输入数据“允许修改入参吗”需要先确认。面试时可以提一句这个想法再根据面试官反馈决定是否真的修改。4.3 搜索二叉树查找别把 BST 当成普通树既然热词里有“搜索二叉树”这里单独讲一下 BSTBinary Search Tree里的 DFS。BST 是排序过的二叉树左子树所有节点值都小于根右子树所有节点值都大于根所以理论上查找节点时利用这个有序性平均复杂度只有 O(log n)。但 DFS 的思维惯性让我们容易犯一个错误把 BST 当成普通二叉树所有节点一律进行三路遍历完全不利用排序信息。这不会错的只是用不上 BST 的优势。正确做法是每一层根据目标值和当前节点值的大小关系只深入一个子树。def search_bst(root, val): if root is None or root.val val: return root if val root.val: return search_bst(root.left, val) return search_bst(root.right, val)这里最关键的是不需要同时递归左右两边。任何一次查找路径上的每一步都只可能去一边。这意味着搜索路径的深度直接由树的平衡程度决定。如果是极端的 BST退化成链表DFS 深度会变成 n再套递归写法就会栈溢出。应对手段是写迭代版查找def search_bst_iterative(root, val): cur root while cur is not None and cur.val ! val: if val cur.val: cur cur.left else: cur cur.right return cur熟悉这个版本之后相关的 BST 区间搜索、最近公共祖先、验证 BST都能很快推出正确的 DFS 结构。5. 常见问题与排查心得5.1 只过样例不过大数据的排查思路这是写 DFS 最容易遇到的一种情形本地小数据测试全对一到大数据或者在线评测就超时或答案错。先看超时。超时的原因绝大多数是剪枝不充分或没有记忆化。DFS 在搜索树庞大的情况下会指数级膨胀只靠“尽量剪枝”很难彻底解决很多问题需要把中间结果缓存下来也就是记忆化搜索。记忆化的本质是把已经计算过的状态存起来下次直接查表。它能把很多指数级的搜索降成多项式级别。再看答案错。大数据下答案错一个典型原因是数据结构选得不对。比如判断“某个元素是否在当前路径中”用了列表每次判断是 O(n)小数据看不出问题数据量上来就会超时换成集合或布尔数组就没事。另一个原因是 hash 类容器引入了随机因素某些语言里字典/哈希表遍历顺序不稳定可能导致不同分支的搜索顺序不同从而影响到“需要保留首次结果”的场景。排查时我有个固定套路先把递归深度上限临时调大排除 RecursionError 对结果的干扰然后用尽量小的数据手动逐行推一遍递归树最后在递归函数开头打印当前状态观察有没有异常分支。打印法是调试腹膜屡试不爽。5.2 无限递归与栈溢出定位方法无限递归是最让人头疼的 DFS 故障因为程序不会立刻报错而是会一直跑直到资源耗尽才崩溃。定位时先思考两个问题状态是不是在重复结束条件是不是永远没机会满足重复状态的发生在写树的时候不常见因为树天然没有环但在图、网格、迷宫这类场景里极其常见。没有 visited 集合或者 visited 维护在错误位置都会出现 A 到 B、B 又到 A 的死循环。结束条件不满足常见于深度目标设错。比如全排列里应该判断len(path) len(nums)但写成len(path) len(nums)那永远不会相等递归会一直超出长度边界。这种错误在小测试里特别容易漏过去。栈溢出的定位方式也很有意思如果你用 Python 收到RecursionError: maximum recursion depth exceeded在报错信息里通常能直接看到递归函数的调用链。Linux 用ulimit -s unlimited临时调大栈空间是一个办法但根本上还是要改写迭代版本。5.3 两个实用调优技巧最后分享两个我实际用下来很有效的调优技巧。第一个是DFSBFS 混合思路。有些迷宫最短路径类问题纯 DFS 穷举所有路径会非常慢因为 DFS 天生不是求最短路的。这时候可以先用 DFS/二分先把“可达性”做出来再用 BFS 去找最短路径。另一种常见混合是“双向搜索”从起点和终点同时跑 DFS两边各走一半深度再汇合搜索量能指数级下降。第二个是为 DFS 写一层函数缓存层。这个思路也常叫记忆化或备忘录。判断是某一个状态是否已经计算过如果计算过直接返回结果。比如字符串切分问题就把“当前起点位置”作为 key把“从当前位置能否成功切分”存起来。由于 DFS 的调用栈天然适合缓存代码上的改动往往只有几行但运行时间可能从数秒降到毫秒。我倒不觉得 DFS 需要背太多模板更重要的是一旦理解了“深入回溯”这套底层机制所有变种都能自然地推导出来。实际写代码时用递归还是手写栈走迷宫还是摆皇后区别只在于状态的定义和剪枝的精准度。把这两个点想明白搜索之 DFS 在绝大多数场景下都能又快又稳地完成任务。