做过一轮算法专项梳理之后我发现一个很有意思的现象DFS深度优先搜索相关题目在题库里看着五花八门从全排列、岛屿数量到二叉树路径、数独求解名字各不相同但真正放到“怎么设计递归函数、怎么管理状态、怎么回溯”这个层面来看核心套路其实很少。网上关于DFS的讨论非常多比如“dfs和bfs算法流程图”“dfs搜索”这类关键词总是被反复搜说明大家普遍卡在同一个点上知道DFS要递归但不知道怎么把一道具体题目套进递归框架里。这篇文章我就基于自己的刷题和实战经验把DFS题目拆成四大核心类别每类给出可复用的模板、关键代码、常见坑点。不论你是准备算法面试、参加程序设计竞赛还是工作中要写搜索型逻辑这套分类思路都值得存一份。我会尽量用大白话讲原理再上代码和排查经验保证你能直接照着用。1. DFS的本质一条道走到黑撞墙才知道回头1.1 递归展开的“状态树”到底长什么样DFS说白了就是“沿着一条路径尽可能深地搜索直到无法继续再返回到上一个岔路口换一条路继续”。这个“岔路口”在代码里就是递归函数的多次调用每条不同的搜索路径对应一个独立的“状态”。给你一个最直白的生活类比你在一个多层停车场找车DFS的做法是随便选一个方向往里走每遇到岔路口就记住位置走到死胡同就退回最近一个没走过的岔路口再试另一条。BFS则是先把当前楼层所有位置看一眼再逐层往下找。这个差异决定了DFS适合“找全部解”“判断是否存在一条合法路径”这类需求因为它天然会把所有可能性完整地展开一遍。代码层面一次DFS调用的完整流程是def dfs(state, 其他参数): # 1. 先判断当前状态是否满足结束条件找到答案 / 走不下去 if 结束条件: 处理答案 return # 2. 枚举当前位置的所有可能选择 for choice in 所有可选选择: # 3. 做选择进入下一层 记录/标记 choice 已使用 dfs(更新后的state, 其他参数) # 4. 撤销选择这就是“回溯”恢复现场 撤销标记很多初学者写DFS会漏掉第4步“撤销选择”导致后续分支被之前的标记污染结果越算越离谱。记住一个心法递归函数进入前什么样返回后就要恢复成什么样。这是DFS四大类题通用的基础规范。1.2 DFS与BFS的分工最短路径找BFS所有解和路径搜索找DFS既然热词里总把“dfs和bfs”放在一起提这里我多对比几句。BFS用队列一层一层往外扩DFS用递归或显式栈一次深入到底。它们处理的问题边界很清晰求“最短路径”“最少步数”“最快到达”这类最优解首选BFS。因为BFS按层扩展第一次搜到目标时就是最短路径。求“所有可能的路径”“是否存在满足条件的组合”“枚举所有排列”首选DFS。因为你要的是全集必须暴力地把状态树完整走一遍。判断“是否可达”DFS和BFS都行差别主要在空间占用DFS递归栈的深度跟路径长度成正比BFS的队列跟当前层的宽度成正比。在树结构里用DFS特别省心因为天然没有环连visited数组都可以省。把这条分界线记牢面试时能少走很多弯路。下面进入正题逐个拆解四大类的模板和实战细节。2. 第一大类排列、组合与子集问题这一类可能是DFS入门最常见、也最容易被细节坑到的一类。核心问题是从一个集合中选元素按某种规则组成排列、组合或子集要求返回所有可能结果。2.1 全排列模板用visited数组防止重复使用全排列的经典题目是“给定不含重复数字的数组nums返回所有可能的全排列”。它的状态树是这样的第一个位置可以选任何元素第二个位置从剩下的元素里选以此类推。所以DFS函数需要记录“我已经选到第几个位置了”“哪些元素已经被用过了”。def permute(nums): n len(nums) res [] used [False] * n track [] def dfs(): # 所有位置都填完了得到一个排列 if len(track) n: res.append(track[:]) # 注意拷贝不能直接append track return for i in range(n): if used[i]: continue used[i] True track.append(nums[i]) dfs() track.pop() # 撤销 used[i] False # 撤销标记 dfs() return res这段代码里有两个细节非常关键。第一res.append(track[:])必须拷贝一份因为track是同一个列表对象后续回溯会不断修改它如果直接append最后得到的结果会全部变成空列表或者同一个最终状态。第二used[i]标记必须与track的push/pop严格配对一旦漏掉还原就会出现“第一个分支把nums[2]用过第二个分支永远选不到nums[2]”的诡异问题。如果nums里有重复元素题目会变成“全排列 II”这时要先对nums排序然后在for循环里加一个去重判断if i 0 and nums[i] nums[i-1] and not used[i-1]: continue。这个判断的直观解释是相同数值的元素在同一层只能被使用一次保证相同前缀的搜索不会重复展开。2.2 组合与子集用startIndex控制选择范围组合问题“从1到n选k个数”与子集问题最大的区别是组合不关心顺序[1,2]和[2,1]是同一种结果。如果还使用全排列那种“每次从所有元素里选”的思路就会出现大量重复。解决办法是引入一个start参数规定每一层只能从start及其之后的元素里选。def combine(n, k): res [] track [] def dfs(start): if len(track) k: res.append(track[:]) return for i in range(start, n 1): track.append(i) dfs(i 1) # 下一层只能选比i大的数字 track.pop() dfs(1) return res子集问题也很简单唯一变化是“收集答案”的时机不同子集不需要等到凑满k个而是每进入一层都可以把当前track存进结果这样自然能收集到所有长度的子集。如果题目要求子集不能重复有重复元素的集合子集同样需要排序并做同层去重。这类题最常见的超时原因是没有利用start缩小搜索范围导致同一个组合被重复枚举。你可以自己跑一个n5, k3的小例子看看使用start前后递归调用次数差了多少倍。3. 第二大类网格与棋盘类搜索问题这一类是在二维网格上做DFS考察点从“集合选数”变成了“坐标移动”。典型场景包括岛屿数量、单词搜索、八皇后、迷宫路径。3.1 岛屿数量最简单的四方向连通块统计“给定一个由1和0组成的网格计算岛屿数量”是DFS入门必刷题。做法是从每个未访问过的陆地格子出发用DFS把整个连通块全部走一遍并标记为已访问每启动一次这样的DFS就说明发现了一个新岛屿。def numIslands(grid): if not grid: return 0 m, n len(grid), len(grid[0]) count 0 def dfs(i, j): # 越界或者是水直接返回 if i 0 or i m or j 0 or j n or grid[i][j] 0: return grid[i][j] 0 # 原地标记防止重复访问 dfs(i1, j) dfs(i-1, j) dfs(i, j1) dfs(i, j-1) for i in range(m): for j in range(n): if grid[i][j] 1: count 1 dfs(i, j) return count这个写法有个很实用的优化直接原地把访问过的陆地改成0省掉了额外的visited二维数组。实战中这个优化不是为了省那点内存而是让代码更简洁不用在四个方向递归前都带上visited[i][j]判断。网格类DFS最容易踩的坑是方向偏移量数组写错。比如四个方向写成[(0,1),(0,-1),(-1,0),(1,0)]没问题但写成[(1,1),(-1,-1)]这种斜向移动就会出大错。建议把方向数组固定成常量每次做网格搜索直接复用减少手写错误。3.2 单词搜索带额外约束的路径搜索“给定一个二维网格和一个单词判断单词是否存在”是网格DFS里更有挑战性的一类因为它要求路径连续、不能重复使用同一格。相比岛屿数量的“覆盖整个连通块”单词搜索更像“沿着某条合法路径验证”。def exist(board, word): m, n len(board), len(board[0]) def dfs(i, j, k): if k len(word): return True if i 0 or i m or j 0 or j n or board[i][j] ! word[k]: return False # 这里必须先用临时标记避免当前路径重复使用同一格 tmp board[i][j] board[i][j] # found (dfs(i1, j, k1) or dfs(i-1, j, k1) or dfs(i, j1, k1) or dfs(i, j-1, k1)) board[i][j] tmp # 恢复现场 return found for i in range(m): for j in range(n): if board[i][j] word[0] and dfs(i, j, 0): return True return False这里最值得学习的点是“临时标记法”进入递归前把当前位置改成特殊字符递归返回后再改回来。它跟visited数组相比省去了每次判断坐标是否在visited中的麻烦缺点是无法同时处理多条交叉路径的共享访问状态但单词搜索这个场景里它刚好够用。如果网格特别大还可以加一个字符频率预判先统计word每个字符出现次数是否都不超过网格中的数量不满足直接返回False这个剪枝能过滤不少必败用例。3.3 八皇后与带约束棋盘搜索剪枝是灵魂八皇后要求“在n×n棋盘上放置n个皇后使它们不互相攻击”核心约束是每行、每列、每条主对角线和副对角线都只能有一个皇后。因为每行只能放一个皇后所以DFS可以按行展开每一行枚举列位置。def solveNQueens(n): res [] col set() diag1 set() # 主对角线i - j 值固定 diag2 set() # 副对角线i j 值固定 queens [-1] * n def dfs(row): if row n: board [] for i in range(n): line [.] * n line[queens[i]] Q board.append(.join(line)) res.append(board) return for c in range(n): d1 row - c d2 row c if c in col or d1 in diag1 or d2 in diag2: continue col.add(c); diag1.add(d1); diag2.add(d2) queens[row] c dfs(row 1) col.remove(c); diag1.remove(d1); diag2.remove(d2) dfs(0) return res这类棋盘搜索的剪枝思路是通用的不要等完整棋盘生成后再验证合法性而是在每一步放置时就用集合检查当前放置是否与已有皇后冲突。用row - c表示主对角线、row c表示副对角线是一个很经典的小技巧建议直接背下来。如果n很大还可以继续用“列、对角线是否可用”的位运算状态压缩但在面试中集合写法已经足够清晰。4. 第三大类树上的路径与状态搜索树上的DFS其实比前两类更简单因为树没有环不需要visited数组递归天然沿着父节点到子节点的方向走。它唯一的难点在于“递归函数返回什么”。4.1 二叉树的路径总和与路径收集面试很高频的一道题是“给你一棵二叉树和一个目标值返回所有从根节点到叶子节点、路径上节点值之和等于目标值的路径”。这个场景的DFS状态是“当前节点”和“到当前节点为止的累计值”。def pathSum(root, targetSum): res [] track [] def dfs(node, remain): if not node: return track.append(node.val) remain - node.val # 只有到达叶子节点且remain为0才算一条合法路径 if not node.left and not node.right and remain 0: res.append(track[:]) dfs(node.left, remain) dfs(node.right, remain) track.pop() dfs(root, targetSum) return res这段时间复杂度是O(n^2)量级的因为每个节点都可能被不同路径的递归访问到但在二叉树场景下n不会特别大所以基本够用。如果你追求更优解法可以引入前缀和字典类似“和为k的子数组”那题的思路但我觉得作为DFS练习先把递归回溯版本写稳更重要。树形DFS里必须注意的一个点是“空节点”处理。如果你在递归开头写if not node: return那么“叶子节点”的判断必须发生在node.left和node.right都为空的那一步而不能把空节点也算作一次答案。我见过很多初学写出的代码把空节点也算成叶子导致结果里多了若干条不存在的路径。4.2 树的最大深度、直径与后序遍历状态汇总除了路径收集树形DFS还有一种非常常见的设计模式递归函数“向上返回一个状态值”父节点利用左右子树的返回值来汇总答案。典型代表是求二叉树直径也就是任意两个节点之间最长路径的长度。def diameterOfBinaryTree(root): ans 0 def depth(node): nonlocal ans if not node: return 0 left depth(node.left) right depth(node.right) ans max(ans, left right) # 经过当前节点的最长路径 return max(left, right) 1 # 给父节点用的最大深度 depth(root) return ans这段代码的核心逻辑是每个子问题只做两件事一是计算经过当前节点的路径长度并更新全局答案二是返回当前子树的最大深度供父节点继续拼接。这种“后序汇总”思路在处理最近公共祖先、二叉树的翻转、判断平衡二叉树时也完全复用。判断平衡二叉树只需要额外加一个abs(left - right) 1就返回-1表示不平衡的剪枝。在我看来树上DFS和网格DFS唯一需要注意的环境差异是树搜索不需要visited因为你从根往下走永远不会走回父节点但如果题目把树给成了node.left和node.right互指、或者允许从任意节点出发就必须考虑环的问题。遇到这种变种时依然要回到图DFS的模板去处理。5. 第四大类图上的路径与连通性搜索图上的DFS是四大类里最考验“环处理”能力的。因为图中可能存在环不加visited控制就会无限递归。但只要把visited的使用时机搞清楚图DFS的模板其实也很固定。5.1 判断可达性与连通分量“给定一个有向图判断从某个节点能否到达另一个节点”这类题目本质就是一次DFS的布尔返回问题。以经典题“课程表”为例判断有向图是否存在环可以给每个节点标记三种状态0表示未访问1表示正在当前递归栈中2表示已经处理完。def canFinish(numCourses, prerequisites): graph [[] for _ in range(numCourses)] for a, b in prerequisites: graph[a].append(b) state [0] * numCourses def dfs(course): if state[course] 1: return False # 在当前路径又遇到自己说明有环 if state[course] 2: return True # 之前已经验证过无环直接复用结果 state[course] 1 for pre in graph[course]: if not dfs(pre): return False state[course] 2 return True for i in range(numCourses): if not dfs(i): return False return True这里的三色标记法非常实用它比单纯用布尔visited多了一层“当前路径”的判断能有效区分“遍历到祖先节点形成环”和“遍历到已经处理完的节点”。我强烈建议每次遇到图上的DFS只要有可能涉及环就直接用三色标记不要用布尔visited。布尔visited在“判断是否到达”时够用但在“判断是否存在环”时会产生误判。5.2 枚举所有路径从起点到终点的全路径搜索另一类高频图DFS是“所有可能的路径”比如LeetCode 797给一个有向无环图返回从0到n-1的所有路径。这类题跟全排列的框架非常像唯一区别是“选择列表”变成了当前节点的所有邻居。def allPathsSourceTarget(graph): n len(graph) res [] track [0] def dfs(node): if node n - 1: res.append(track[:]) return for nxt in graph[node]: track.append(nxt) dfs(nxt) track.pop() dfs(0) return res因为题目明确说是有向无环图所以不需要visited。如果题目不保证无环就必须在递归入口判断当前节点是否已经在track里否则会出现无限路径。这个“路径中节点唯一性”的约束也是DFS常见变种。要特别提醒的是图DFS里的track[:]拷贝同样不能省略不然结果会全部变成同一个最终状态。5.3 最短路径问题千万别用DFS实战中我见过不少人遇到“迷宫最短路径”“最少步数到达终点”这类问题下意识就写DFS结果要么超时要么勉强通过。这是个方向性错误DFS求最短路径会遍历大量非最优分支甚至在带环图里退化成指数级搜索而BFS天然按层扩展找到终点的深度就是最短步数。判断依据很简单如果问题问的是“最少几步”“最短路径”立即切换到BFS如果问题问的是“是否存在”“有多少种方案”“列出所有可行解”DFS才是正确的选择。记住这条能帮你在面试或竞赛中省下大量时间。6. 实战经验常见问题与排查技巧实录这里我把自己在练习和辅导中反复遇到的几类问题整理成一份速查表每一个都是我实际踩过或看别人踩过的坑。现象根本原因解法思路结果全是空列表或重复的同一个列表res.append(track)没有拷贝改成res.append(track[:])答案数量偏少甚至很多分支没走到递归中提前return的条件写错检查终止条件是不是把不该结束的状态拦掉了结果大量重复去重失效或没有去重排序 同层重复值跳过结果顺序看着对但缺了一些组合组合问题没加start参数组合/子集问题必须用start缩范围运行超时没有剪枝搜索空间爆炸在递归入口提前判断不可能的分支并返回网格类题目越界/死循环方向数组写错或未标记访问检查方向偏移量与原地标记是否生效图类题目栈溢出没处理环用三色标记替代布尔visited修改了全局变量但没恢复回溯步骤缺失push/pop操作必须成对出现在递归前后针对“结果重复”这类问题我想再展开讲一个排查技巧直接打印递归状态。你可以在DFS函数里加一个depth参数然后这样打印def dfs(depth, state): print( * depth fenter state{state}) ... print( * depth fexit state{state})看到缩进的enter和exit成对出现就能直观发现哪个分支没有正确回溯。真实调试时这个方法比断点高效很多因为你一眼能看到整棵搜索树的走向。另外有几个容易被忽略的实战细节我特别强调一下递归函数的参数设计要尽量“小”把数组、集合这种全局性的数据结构放成外层变量递归参数只放“当前选到哪个位置”“当前累计值”这类会随路径变化的小状态。这样不仅代码清晰也不容易爆栈。用非递归手写栈同样可以实现DFS但需要自己维护状态还原代码复杂度更高。建议先把递归版写熟遇到深度特别大的题目比如数独再考虑手写栈或迭代加深。在竞赛场景DFS的递归深度过深可能触发递归栈上限这时候可以用sys.setrecursionlimit(1000000)Python临时提高限制但还是那句话剪枝优先靠改栈帧深度不是长久之计。7. 训练路线总结与我的个人体会最后给一个我认为比较合理的DFS刷题顺序你可以直接照着练第一阶段全排列、子集、组合三类基础模板各做2题目标是能默写出“选择-递归-撤销”三件套。第二阶段岛屿数量、单词搜索、八皇后目标是掌握网格坐标移动和剪枝思路。第三阶段二叉树路径总和、二叉树直径、最近公共祖先目标是理解“递归返回值”这种后序汇总模式。第四阶段课程表、所有可能的路径、迷宫寻路目标是熟练运用三色标记并分清DFS与BFS的适用场景。按这个顺序练下来你会慢慢形成一个本能反应拿到新题第一件事不是马上敲代码而是想清楚递归函数的“状态参数”是什么、“终止条件”是什么、“如何把子问题结果合并成父问题答案”。这三个问题想明白了DFS题目基本就只剩细节了。我个人在实际操作中的一个体会是四大类分类本身不是目的它真正的价值是帮你快速定位“这道题该怎么设计递归框架”。全排列和组合考的是“选择列表的构造与去重”网格和棋盘考的是“坐标移动与剪枝”树考的是“后序状态汇总”图考的是“环处理与可达性”。能准确说出题目属于哪一类你的解题速度至少提升一倍。希望这篇梳理能帮你把DFS这块硬骨头啃下来后面遇到再离谱的搜索题也能心里不慌。