深度优先搜索DFS详解：从递归模板到回溯剪枝与记忆化优化

我一直觉得算法题里最性感的比喻就是“闯关取宝藏”。打开题目，你站在一个迷宫入口，面前分了几条岔路，各处藏着宝箱，有的岔路尽头是死胡同，有的绕一圈又回到原点。你要做的就是摸清每一条路，把藏在最深处的宝物找出来。这不就是深度优先搜索（DFS）干的事吗？

深度优先搜索，英文叫 Depth-First Search，简称 DFS。这个名词在算法面试、信息学竞赛里出现频率极高，凡是学过数据结构的人多少都听过。但很多人对它的理解停在“递归遍历树”这个层面，换个场景就不知道怎么下手。这篇文章我就借着“闯关取宝藏”这张图，把 DFS 的完整玩法拆开揉碎：从它到底在搜索什么，到递归模板怎么写，再到几个经典变体和剪枝优化，最后聊聊“什么时候该用 DFS、什么时候该换 BFS”。不管你是刚学算法的萌新，还是准备机试刷题的老手，应该都能从中挖到自己需要的东西。

1. 从“闯关取宝藏”说起：DFS 到底在找什么

1.1 一条路走到底，不撞南墙不回头

想象一个非常原始的闯关地图：你从起点出发，每个房间有四扇门，每扇门通向一个新的房间。宝藏在某个房间的箱子里。规则是，每进一个房间你可以选择一扇门进去，进去之后不管你选哪一扇，只要这个新房间还有门，你就继续往深处走，绝不因为“感觉这条路不对”就立刻折返。

这就是 DFS 的核心策略：优先往深处探索，走到死胡同（没有门、没有子节点、没有可选状态）才回头，回头之后换一扇门再往深走。整个过程靠“不断下潜 + 触底回退”循环推进，直到所有房间都被造访过。

这个策略放在算法里，对应一个非常朴素的问题：给定一个状态，它可以转移到若干个子状态，每个子状态又继续扩展子状态，你要把整棵状态树完整走一遍。DFS 给你的承诺是：只要每个状态都被访问过，你就能遍历所有可能的路径，找到符合条件的那个“宝藏”。

很多人第一次接触 DFS 会疑惑：这不是暴力枚举吗？对，DFS 本质上就是暴力枚举的一种实现方式。它不聪明，但它“彻底”。在问题规模可控的前提下，DFS 可以保证不遗漏任何一个解，这正是它作为搜索算法基石的原因。你后面学的回溯、剪枝、记忆化搜索，都是在“彻底”这个基础上做的优化，而不是换了一种搜索哲学。

1.2 “深度优先”里的深度到底是什么

为了说清楚这个问题，得引入“搜索树”这个概念。任何状态转移问题都可以画成一棵倒着的树：根节点是初始状态，每个节点的子节点是它下一步可达的状态。这棵树的层数，就是从初始状态到当前状态经过的转移次数。

BFS（广度优先搜索）是按层推进：先把第一层所有节点看一遍，再看第二层、第三层。DFS 不是这样，它会顺着某个分支一路走到最底层，也就是走到这条路径能到达的最深状态，再退回来试探其他分支。这里的“深度优先”，指的就是分支的纵深方向。

打个比方：BFS 像按楼层扫描一栋楼，逐层巡视每个房间；DFS 像从一楼某个电梯间一口气坐到顶楼，再下来换另一个电梯间。两种方式都能检查完全部房间，但移动路径完全不同，这个区别后面会直接影响你能解决的问题类型。

1.3 为什么“闯关取宝藏”是 DFS 的标准画面

“闯关取宝藏”这个描述，几乎把 DFS 的关键构成要件全说全了：

• 有一个明确的起点（初始状态）
• 每一步有多个选择（状态分叉）
• 选择之后进入新的状态，可能还有更多选择（状态层叠）
• 某些选择会导致失败，需要回头（回溯）
• 目标是找到某个满足条件的终态（命中宝藏）

这一套流程，放在编程里就是三个核心机制：递归表示状态层叠、循环遍历所有分支、状态还原实现回退。

你去看任何 DFS 代码，都逃不出这个骨架：

void dfs(当前状态) { if (当前状态是目标) { 记录答案; return; } for (每个可转移到的下一状态) { 做选择（标记状态）; dfs(下一状态); 撤销选择（恢复状态）; } }

后面所有花里胡哨的写法，都是在这个骨架上叠加剪枝条件、边界判断或者记忆化缓存。所以只要你把这个画面在脑子里立住了，DFS 就从一个抽象名词变成了具象的过程，后面写代码的时候就不容易慌。

2. 手写 DFS：递归模板、回溯还原与栈的实现细节

2.1 能直接跑的递归模板

先给一个最通用的 DFS 模板，场景是“在一棵树上收集所有从根到叶子的路径”。这个场景熟悉一下，因为大多数 DFS 写法都可以从它变形而来：

def dfs(node, path, result): # node 表示当前节点 # path 表示从根节点到当前节点的路径记录 # result 用于收集满足条件的路径 if node is None: return path.append(node.val) if node.left is None and node.right is None: result.append(path[:]) # 到达叶子，复制一份路径保存 else: dfs(node.left, path, result) dfs(node.right, path, result) path.pop() # 回溯：撤销当前节点的选择

这套代码看着简单，但里面藏着三处关键。

第一处，path[:]复制。如果你直接把path存进result，后续path.pop()会把已经存好的路径也改掉，因为列表是引用传递。这个小问题我在实际刷题踩过不止一次，新手尤其容易中招。

第二处，path.append在递归前，path.pop()在递归后。DFS 的状态表示中，当前路径是一个随递归深度不断变化的值。进入更深节点前你先记录当前选择，回溯时再把它删掉，这样同一份记录在不同深度表达不同路径，空间复杂度是 O(深度)，而不是 O(节点数)。很多面试官问 DFS 的空间复杂度，答案就是 O(h)，h 是搜索树深度。

第三处，if node is None放在开头，用来兜住空节点。这个判断也可以放在递归调用前，比如写成if node.left: dfs(...)，两种写法各有千秋，前者代码更统一，后者性能略优。我习惯用前者，因为不容易漏边界。

2.2 手动维护栈的迭代版，以及它和递归的关系

递归版能跑，但有些场景不允许用递归。原因后面会说，常见情况是“递归深度超过了系统栈上限”。这时候你需要一个迭代版本，原理一模一样，只是把系统帮你维护的调用栈换成自己声明的栈对象：

def dfs_iterative(root): if root is None: return [] stack = [(root, [root.val])] result = [] while stack: node, path = stack.pop() if node.left is None and node.right is None: result.append(path) if node.right: stack.append((node.right, path + [node.right.val])) if node.left: stack.append((node.left, path + [node.left.val])) return result

注意这里为什么先压node.right再压node.left。栈是后进先出，你先压右子树，左子树就会在栈顶，下一次先被弹出。这样循环展开后的访问顺序和递归版本保持一致，仍然是“先左后右”。

把递归版和迭代版对照看，你会理解一件特别重要的事：递归调用并不是什么神秘机制，它只是把当前的局部变量和返回地址压入系统栈，函数返回时再弹出。你完全可以用显式的栈对象复现这套行为。理解这一点之后，很多所谓“递归转迭代”的算法题就都通了。

2.3 被问烂的回溯，状态还原为什么如此重要

回溯这个词，经常和 DFS 放在一起提，但它不是另一个算法，而是 DFS 里的一个操作：当你从一条分支返回上一层状态时，必须把当前分支带来的状态修改撤销干净。

还是用“闯关取宝藏”来想。你走了一条岔路，深入了几个房间，最后发现此路不通，要回到分岔口换一条路。如果回来的路上你没有把走过的门复位，下一次从分岔口出发时你会以为那些房间还是“已解锁通行”的状态，这样就会漏掉探索线路，甚至走进环里死循环。

放在代码层面，状态污染是 DFS 里最常见的 bug。比如你用一个布尔数组标记哪些格子已经访问过，进入时标记为 True，退出时如果你忘记改回 False，另一条分支就无法访问这些格子。DFS 的答案就会少算。

有三类状态需要你特别注意是否要还原：

• 访问标记数组（visited），通常递归前标记，回溯后清理
• 当前路径记录（path），用 push/pop 维护
• 全局计数器或累计值（比如路径和、已选元素和），如果在循环体内累加，回溯时要减回来

但注意，并非所有状态都要还原。如果是“这条分支选了某值，就不允许其他分支选”这类互斥条件，你可能希望通过全局集合去重，那就不适合在回溯时无脑清理，要具体看题目要求。经验法则是：状态是依附于“当前路径”还是依附于“全局搜索结果”，前者必须还原，后者不必。

3. 三张经典藏宝图：全排列、迷宫寻路与连通块计数

光看模板还不够，得动手处理几道经典题。我把 DFS 最常见的三种场景各挑了一道，这三道题覆盖了大部分 DFS 变体的套路，吃透它们，再遇到新题基本就是把模板往上套。

3.1 全排列：DFS 做排列组合的标准姿势

题目：给定一个不含重复数字的数组nums，返回所有可能的全排列。

全排列可以说是最经典的 DFS 入门题。每个位置尝试放一个数字，已经用过的数字不能再放，这就是闯关图中“每个房间的门不能重复进”的抽象。

def permute(nums): result = [] path = [] def backtrack(used): 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]) backtrack(used) path.pop() used[i] = False backtrack([False] * len(nums)) return result

这里的used数组就是访问标记，标记某个下标是否已经在当前路径中使用过。每次递归前标记，递归后立刻还原，保证不同分支之间互不干涉。搜索树的深度是len(nums)，每层可选数字的数量逐层递减，第一层有 n 个选择，第二层 n-1 个，第三层 n-2 个，所以总状态量是 n!，这也是全排列复杂度的来源。

需要注意的一个细节是剪枝条件if used[i]: continue。这一步不是优化，而是正确性保证。如果不做检查，同一个数字会被重复使用，路径长度永远无法到达 n，或者同一个排列会被生成无数次。DFS 的“去重复选”要么靠标记数组，要么靠排序后跳过相邻相同值，前者处理显式重复选择，后者处理隐式重复结果。

3.2 迷宫寻路：二维网格上的上下左右状态转移

二维网格是 DFS 的另一大主场。给你一个迷宫，0 表示空地，1 表示墙，从左上角出发，问能否走到右下角。这类题的状态转移不再是数组下标的选择，而是坐标的上下左右移动。

def can_exit(maze): rows, cols = len(maze), len(maze[0]) visited = [[False] * cols for _ in range(rows)] directions = [(0, 1), (0, -1), (1, 0), (-1, 0)] def dfs(x, y): if maze[x][y] == 1: return False if x == rows - 1 and y == cols - 1: return True visited[x][y] = True for dx, dy in directions: nx, ny = x + dx, y + dy if 0 <= nx < rows and 0 <= ny < cols and not visited[nx][ny]: if dfs(nx, ny): return True return False return dfs(0, 0)

这个题的难点在于方向控制。directions数组是二维网格 DFS 的万能方向表，如果允许斜向移动就扩成 8 个方向。0 <= nx < rows and 0 <= ny < cols这个边界检查一定要写在访问前，否则数组越界直接报错。

关于visited要不要在回溯时还原，这里有个重要区别：如果题目只问“是否存在一条可行路径”，你标记visited后就不需要还原，因为这条路走不通，换成从其他方向进入这个格子大概率也走不通，保留标记还能避免大量重复搜索。但如果题目问的是“所有可能路径”，你必须还原visited，因为同一格可以作为不同合法路径的一部分。判断依据很简单：你是要一个解还是所有解。

3.3 连通块计数：把整个地图染色

第三类高频题是连通块计数。比如给一个二维矩阵，1 表示陆地，0 表示水域，数一数一共有多少块相连的陆地。这类题在面试中考得非常多，LeetCode 上的“岛屿数量”就是原题。

思路非常干脆：每发现一个未访问的陆地，就对这个格子执行 DFS，把它所在连通区域的所有陆地都标记为已访问，然后计数器加一。这样每个连通块只会被计数一次。

def num_islands(grid): rows, cols = len(grid), len(grid[0]) count = 0 def dfs(x, y): if x < 0 or x >= rows or y < 0 or y >= cols or grid[x][y] == '0': return grid[x][y] = '0' 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': count += 1 dfs(i, j) return count

这个写法里有个极其聪明的地方：不额外申请visited数组，而是直接把遇到的陆地改成水，也就是“沉岛”。这样可以避免空间开销，也让代码更短。面试时如果面试官问怎么优化空间，这就是答案。

但要注意，沉岛操作的前提是允许修改原数组。如果题目要求原数组不可变，你得单独开一个visited二维数组，或者在原数组上用另一套标记位。这个取舍要在动手前想清楚。

连通块计数的本质，是把 DFS 当作“蔓延工具”使用。你从一个点出发，尽可能大步向外扩展，直到把整个连通区域走遍再停下。这种用法在图论里对应“遍历整个连通分量”，也是后续学习 Tarjan 算法、割点桥、强连通分量等高级图论算法的基础直觉。

4. 复杂度、剪枝与记忆化：什么时候该回头，什么时候该放弃

4.1 DFS 的时间复杂度为什么经常是爆炸性的

DFS 的时间复杂度，绝大多数情况下等于“搜索树总节点数 × 每个节点的处理成本”。也就是说，它取决于你的搜索空间有多大。

拿全排列来说，搜索树第一层有 n 个选择，每层依次递减，节点总数大约为 n!。n 取 20 的时候，20! 约等于 2.4×10^18，这个数字已经大到任何机器都无法在可接受时间内完成计算。所以如果你发现自己的 DFS 题在 n 稍微大一点就超时，先不要怀疑是代码写慢了，而是搜索空间本身就爆了。

正因如此，实际工程和竞赛里，单纯的 DFS 很少直接用在规模较大的问题上，几乎总会搭配剪枝、记忆化等手段。你能优化的是“别让 DFS 去访问明显没希望的分支”，而不是让 DFS 本身飞起来。

4.2 剪枝的本质就是在搜索树上砍枝叶

剪枝，简单说就是提前判断某一个分支不可能找到解，就不走进去。这个判断必须丢不了正确答案，否则就是误剪。

常见的剪枝来源有四类：

• 边界剪枝：状态越界、超出棋盘、不满足坐标范围，直接 return
• 可行性剪枝：已经不可能到达目标。比如要找和为 K 的路径，当前累计和已经超过 K，后面全是正数就不可能再回到 K
• 最优性剪枝：已经找到可行解，但当前路径长度已经大于已知最优解，就没必要继续走长路径
• 对称性剪枝：某些状态搜索次序不影响答案，可以跳过重复情况，比如排列组合中“保证下一步的选择有序”来避免重复排列

比如迷宫寻路中我前面用visited标记避免重复进入格子，就是一类“防止搜索空间退化成环”的剪枝。没有这个剪枝，DFS 甚至会无限循环。很多初学者以为 DFS 总要遍历完所有状态才算完，其实剪枝的意义正在于：能明确判定为无望的状态，直接不进去。

但剪枝也有代价。每次递归进来都要先做一组判断，这些判断本身需要计算成本。判断逻辑写得过于复杂，哪怕砍掉了很多分支，也可能因为计算量抵消收益。所以剪枝要挑那些“判定成本低但排除能力强”的条件，优先做边界检查，再尝试最优性剪枝。

4.3 记忆化搜索：把重复子问题缓存起来

有一种特殊场景：DFS 过程中同一个状态会被多次访问，每次访问都重复计算一大棵子树。这种浪费可以通过记忆化消除，也就是把某个状态的 DFS 结果存进缓存，再次遇到直接返回。

经典例子是“爬楼梯”或“斐波那契”：当你从不同路径到达同一个台阶数时，后面的选择是完全重复的。硬走 DFS 会导致指数级复杂度，而加上缓存后，每个状态只计算一次，复杂度降成 O(n)。

def climb_stairs(n): from functools import lru_cache @lru_cache(None) def dfs(i): if i <= 2: return i return dfs(i - 1) + dfs(i - 2) return dfs(n)

记忆化搜索在形式上仍然是一个 DFS，但它避开了对重复状态子树的重复遍历。看到“重复子问题”这个词，你要想到动态规划。事实上记忆化搜索是自顶向下的动态规划，普通 DP 是自底向上的填表，两者能解决的问题高度重合。区别在于，记忆化搜索不用规定填表顺序，代码结构更像暴力搜索，对复杂状态转移更容易写对，代价是递归调用有额外的栈开销。

理解这个关系很重要：DFS 不是动态规划的对立面，而是动态规划的入口。遇到一个题目你还没想清楚递推公式，先写成暴力 DFS，再加上缓存做记忆化，往往能顺理成章过渡到一个高效解法。这也是面试里非常推荐的思路，先保证正确，再谈优化。

4.4 当递归深度撞上系统栈上限，怎么办

递归版 DFS 在极端情况有个物理限制：调用栈深度是有上限的。Python 的默认递归深度大约在 1000 层，超过会抛RecursionError。比如你要在 2000×2000 的网格上做连通块染色，递归深度可能一下到几十万，系统栈直接爆掉。

遇到这个情况，有几种处理方式：

• 调高递归上限：sys.setrecursionlimit(10**6)，在竞赛中常见，但只是提高上限，不是无限；而且递归调用本身开销大，容易卡时间
• 改成显式栈的迭代版：就是前面 2.2 小节的做法，不受递归深度限制
• 换一种算法：如果问题可以用 BFS 或并查集解决，何必跟 DFS 的死磕

我的实际经验是：本地刷题可以用setrecursionlimit一劳永逸，但在机试或比赛环境里，建议优先考虑迭代版和 BFS，避免环境对递归深度有额外限制时手忙脚乱。

5. DFS 与 BFS 的分岔路口：选错搜索顺序的代价

5.1 一张图对照 DFS 和 BFS 的性格差异

处理图论和搜索问题时，DFS 和 BFS 经常是同一道题的两条不同路线。搞清楚它们的性格差异，才能做出正确的算法选型。我整理了一个对比表：

空间复杂度这个点值得一提。如果搜索树的深度很大但每层分叉不多，DFS 占用的栈空间可能很可观；如果搜索树的深度不大但每层节点爆炸，BFS 的队列会先撑不住。所以选择哪种搜索，不只是“能不能求出答案”的问题，也是“空间受不受得了”的问题。

5.2 最短路径别逞强用 DFS，存在性路径优先 DFS

最典型的选型陷阱就是最短路径。如果你要找的是“从 A 到 B 的最少步数”，直接用 BFS，大概率最省心。用 DFS 也能求，你可能会想“我把所有路径都找出来，取最小值不就行了”。这在连通图规模小的时候确实可行，但搜索空间一爆炸，DFS 会遍历大量没必要的路径，复杂度很快就失控。

但反过来，如果你只是想知道“到底有没有一条路能从起点到终点”，DFS 有个很大的优势：它可以一边探索一边尝试，如果答案藏在某个很深的分支里，DFS 能很快钻进去找到它，而 BFS 要一层一层地扫描到那么深的位置，可能已经铺开海量节点了。

拿前面的迷宫题来说，如果地图是二维网格，我一般会先问自己一句：题目问的是“能否到达”还是“最短几步”。前者默认 DFS，后者直接切 BFS。这个判断在面试中价值巨大，因为很多候选人不是在写不出代码，而是选错了搜索策略，导致写了半天还要推翻重来。

5.3 我的实战选型习惯与一条独门判断口诀

分享一个我自己的选型标准，虽然不是严格的数学结论，但实战中相当好用：

状态空间是层层递进的，且目标是最短路径、最小步数、最优层级相关的问题，选 BFS；状态空间是树形分叉的，目标是要罗列所有路径、判断可达性、处理连通块或回溯枚举的，选 DFS；如果状态之间存在大量重复子问题，选“记忆化 DFS”。

另外，有些题目天然就是 DFS 的，比如全排列组合、子集生成、八皇后这类“回溯枚举”题。它们的特点是：每一步做一个选择，到了某个深度判断是否满足条件。这类题你要是非用 BFS，也不是不行，但状态管理会变成一个噩梦，写出来的代码丑到自己都不想看。反过来，网格最短路径土味 BFS 基本三分钟写出来。所以先判断题型，再决定策略，是一道搜索类题目拿分的关键。

在“闯关取宝藏”这个场景里，如果你的目标是“把整个迷宫里每个房间都逛一遍，把所有能拿的宝箱全找出来”，DFS 毫无疑问是对的路径；如果你的目标是“最快找到离起点最近的那个金色宝箱”，那就得果断换 BFS，别在 DFS 的死胡同里耗太久。

这套思路想通了，再回头看那些围绕 DFS 的题目，你会发现它们不再是离散的碎片，而是同一个策略在不同地图上的反复演练。我自己刷了上百道搜索题后最大的感受是：搜索题拉不开智商差距，拉开的是你对搜索树形态的理解深度。把状态怎么转移、什么条件可以剪枝、什么情况下该换个搜索策略这几点吃透，大部分搜索题都是送分题。