深度优先搜索DFS：从递归回溯到剪枝优化完整指南

写在前面这篇其实是给一个学弟的私信回复整理出来的。他在牛客上刷到一道带回溯的DFS题卡了一整晚来问我到底怎么才能掌握DFS。我回他的第一句话是DFS不难难的是你一直在背模板没搞懂它在你脑子里和编译器里到底是怎么跑的。这篇文章就是把那封长信重新梳理了一遍顺便补了几个我当年踩过的深坑希望能让正在被dfs——偏难劝退的人把这块硬骨头真正啃下来。1. 为什么全网都在说DFS偏难先定位真正的痛点先说结论DFS深度优先搜索的核心思想一句话就能说完——沿着一条路走到黑走不通了再回头换一条路走。这句话你让任何一个培训班老师来讲三分钟就能讲完。但为什么一到做题、一到写代码就变成偏难了我的观察是90%的人卡住根本不是卡在深度优先这个思路上而是卡在三件具体的事情上第一递归函数的执行流程。很多人学DFS之前只写过循环和顺序执行的代码脑子里默认函数是一行一行往下跑的。但递归不一样它会在一个函数还没执行完的时候又把自己调用一遍形成一个套娃结构。代码的物理执行顺序和书写的逻辑顺序完全是两套秩序不把这个搞明白你连调试都不知道从哪里下手。第二状态的回溯与恢复。这是DFS里最阴间的一环——为什么有的代码在递归之后要撤销一个操作有的代码又不用什么时候需要恢复现场什么时候不需要判断错了轻则结果错误重则栈溢出而且这种错误极度隐蔽编译器不会报错逻辑上看着也没问题就是答案不对。第三递归的终止条件设计。什么时候该停下来是到达目标状态就停还是遍历完所有状态才停终止条件写多了递归提前结束、结果不完整写少了无限递归、直接爆栈。这一环非常考验你对问题边界的理解。所以与其说DFS难不如说递归的执行模型、状态管理、边界设计这三件事叠加在一起形成了一道认知门槛。本篇不打算给你一堆记不完的模板而是把这三个痛点一个一个掰开揉碎最后再用一个完整的例子串起来跑一遍。2. 从全排列看DFS的底层执行模型理解递归套娃2.1 全排列题目先明确我们在解决什么问题不考虑那些花哨的题目包装DFS最经典、最适合入门的载体就是全排列问题给定一个不含重复数字的数组nums [1, 2, 3]返回所有可能的全排列。所谓全排列就是所有可能的排列方式[1,2,3]、[1,3,2]、[2,1,3]、[2,3,1]、[3,1,2]、[3,2,1]一共3的阶乘6种。你去看网上几乎所有DFS教程第一道题都是它。这不是巧合而是因为全排列完美包含了DFS的三大核心要素递归结构、路径记录、状态标记。把这题吃透后面遇到组合、子集、迷宫、岛屿、数独等等都是同一套骨架换皮。2.2 最朴素的DFS写法先跑起来再谈优化先看第一版代码用C语言写后面所有分析都基于C因为C的递归调用栈最直观而且热搜里也确实有dfs算法c语言代码#include stdio.h int nums[3] {1, 2, 3}; int visited[3] {0}; // 标记每个数字是否被用过 int path[3]; // 记录当前排列 int n 3; void dfs(int depth) { if (depth n) { // 已经选满了n个位置输出一个排列 for (int i 0; i n; i) { printf(%d , path[i]); } printf(\n); return; } for (int i 0; i n; i) { if (visited[i]) { continue; // 这个数字已经在当前排列里了跳过 } visited[i] 1; // 标记已使用 path[depth] nums[i]; // 当前位置选中它 dfs(depth 1); // 继续选下一个位置 visited[i] 0; // 回溯撤销标记 } } int main() { dfs(0); return 0; }这段代码逻辑上非常清晰。但我知道很多人第一次看这段代码的时候是懵的这个dfs(depth 1)执行完之后代码怎么就回到visited[i] 0这一行了它回到的到底是什么东西的这一行这就是递归让人眩晕的根源。你需要的不是用眼睛看而是亲眼看着它在调用栈里压栈、弹栈的过程。2.3 手推递归调用栈看懂一次压栈和弹栈的完整生命周期把上面代码的第一次完整执行路径画一遍。为了叙述方便我管dfs(0)叫第0层调用dfs(1)叫第1层调用以此类推。一、从dfs(0)开始。第0层函数里depth 0进入for循环i 0visited[0]为0所以选中nums[0] 1即path[0] 1然后visited[0] 1接着调用dfs(1)。注意此时第0层的for循环只执行到一半被挂起了。第0层函数的变量i当前值0、visited数组的状态、path数组的状态全部被压入系统调用栈。它暂停在那里等待dfs(1)返回后再继续执行visited[i] 0。二、进入dfs(1)。这是第1层depth 1重新进入自己内部的for循环注意这个for循环是从i 0重新开始跑的。i 0时visited[0]已经是1了跳过i 1时visited[1]还是0选中nums[1] 2path[1] 2visited[1] 1调用dfs(2)。第1层的for循环也挂起。三、进入dfs(2)。第2层depth 2for循环i 0被跳过i 1被跳过i 2可用选中nums[2] 3path[2] 3visited[2] 1调用dfs(3)。四、进入dfs(3)。第3层depth 3条件depth n成立输出1 2 3然后return。这一层结束它从调用栈里被弹出控制权交还给第2层调用它的那个位置。五、回到第2层的dfs(depth 1)这一行之后紧接着执行visited[i] 0。第2层的i是2所以visited[2] 0。然后for循环继续i变成3超过n第2层的for循环跑完dfs(2)函数结束弹出回到第1层。六、回到第1层调用之后执行visited[1] 0第1层的i是1。然后第1层的for循环继续i 2visited[2]现在是0被第2层撤销了所以选中nums[2] 3path[1] 3visited[2] 1调用dfs(2)。接下来在dfs(2)里i 0被跳过i 1可用选中nums[1] 2path[2] 2visited[1] 1调用dfs(3)输出1 3 2然后逐层返回、撤销……看到关键了吗**每次从下一层返回都会回到调用它的那一层的刚刚调用的那一句之后把这层函数自己当时的状态恢复出来。**这就是为什么深度优先能走到底再回头的物质基础——它不是靠什么神奇的逻辑记录路径而是靠系统调用栈天然地把每一层函数的局部状态都保存了。所以理解DFS的第一把钥匙是递归不是调用自身这么简单而是一个函数在栈上不断复制自己、压栈、然后反向弹栈的过程。3. 回溯的本质为什么有的状态要恢复有的不用3.1 回溯到底回溯的是什么回溯这个词其实很玄学。说白了回溯就是在递归返回前把当前层对全局状态所做的修改撤销掉让状态回到进入这一层之前的样子。为什么需要撤销因为后续的分支共享同一片状态空间。在全排列里visited数组就是全局共享的。你选中了数字2如果不把它撤销那在下一个分支里数字2就永远不可用了那后面的排列就全错了。举个例子dfs(1)里选了nums[1] 2生成排列如果递归返回后不撤销visited[1]一直等于1那么第二层试图生成一个以3开头的排列时数字2永远选不了1 3 2这个排列就永远生成不了。所以回溯的本质是保证每次递归调用都是干净地进入下一层。但这里有个非常容易混淆的坑不是所有修改都需要撤回。最常见也最经典的例子是求子集和组合问题。看这段组合求和代码#include stdio.h int nums[3] {1, 2, 3}; int path[3]; int pathLen 0; // 求所有子集 void dfs(int start) { // 每进入一层当前path就是一个子集先输出 for (int i 0; i pathLen; i) { printf(%d , path[i]); } printf(\n); for (int i start; i 3; i) { path[pathLen] nums[i]; // 选当前元素 pathLen; dfs(i 1); // 下一层从下一个位置开始 pathLen--; // 撤销退回pathLen } } int main() { dfs(0); return 0; }这个代码里path里要存放当前的组合内容递归返回后pathLen--相当于把刚才加入的元素从逻辑上删除。这里确实需要撤销因为你不能让它一直留在path里。但是注意那个visited数组它在全排列里也用来标记数字是否已使用。那我再举一个不需要显式撤销的变体例如二叉树的所有路径问题。访问路径是以参数形式往下传的比如char *path每一层拿到的是父层传下来的副本或者新拼接的字符串返回后父层的path字符串根本没变——这时候你压根不需要撤销因为状态没有共享而是复制传递。3.2 判断是否需要恢复现场的三个黄金法则我给自己总结过三条判断标准对初学者特别管用这个状态变量是所有递归分支共享的吗如果是并且后面的分支依赖它的正确值那必须恢复。典型全排列的visited。这个状态是局部持有、天然隔离的吗如果是按值传递、或者每层都新建那就不用手动恢复。典型递归函数的整型参数、局部变量。这个状态是最终结果的一部分吗如果它在每个节点都要输出、作为路径的一部分被记录那要区分——记录到结果集的时候需要拷贝而不能等递归返回后继续修改。我见过太多人在组合题里用了visited数组却不知道怎么恢复或者在全排列里把自己写的pathDepth恢复错了位置。其实这三个法则能解决绝大多数问题。我再分享一个实战技巧**当你拿不准要不要恢复时就在递归调用前后各打印一遍当前状态看看到底被改了什么、需不需要复原。**第一次这样做虽然慢但对建立直觉极其有效。3.3 回溯的复杂度为什么说DFS是指数级暴力回溯的本质是遍历所有可能随之而来的代价就是状态空间爆炸。全排列的复杂度是 O(n!)子集的复杂度是 O(2^n)组合数也是指数级。拿n20的全排列来说20!约等于2.4乘以10的18次方这已经是普通计算机跑不完的量级了。所以DFS天然是暴力搜索家族的一员。但正因为它是暴力搜索它才是后面一切聪明算法动态规划、分支限界、剪枝的基础。你连暴力都不会写更谈不上优化。很多偏难题目的本质其实是DFS 剪枝剪枝就是让你从傻傻地遍历所有状态变成提前知道某些分支没前途直接砍掉。这个环节单独拿出来说是因为它直接决定了DFS能不能在生产级问题里落地。后面第5节我会专门讲剪枝的实践。4. 经典DFS实战迷宫最短路径全流程带注释现在把前面所有概念放到一个真实的题目里跑一遍。我挑的是很多学校数据结构课程里都会有的迷宫寻路问题它比全排列多了二维状态边界判断最优解更新是衔接入门和进阶最好的题目。4.1 题目与思路为什么迷宫天然适合DFS假设有一个N x M的二维矩阵1表示墙0表示可以走的路。给定起点(1,1)和终点(N,M)求从起点到终点的路径条数或者最短步数每个格子一步。为什么迷宫问题天然适合DFS因为迷宫的整个搜索空间就是一个树状结构你在每个格子都有上下左右四个选择选了一个又面临四个选择……这和全排列里面选了第一个数后剩余数面临新的全排列是同一套逻辑。不同之处在于迷宫需要额外处理边界和墙壁而且它的状态是位置坐标而不是哪个数字用过了。4.2 带注释的C语言完整实现#include stdio.h #define N 4 #define M 4 // 0: 可走, 1: 墙 int maze[N][M] { {0, 0, 1, 0}, {0, 1, 1, 0}, {0, 0, 0, 0}, {0, 1, 0, 0} }; int visited[N][M] {0}; // 标记走过防止原地转圈 int minSteps 999999; // 记录最短步数 int pathCount 0; // 记录路径条数 // 方向数组上、下、左、右 int dx[4] {-1, 1, 0, 0}; int dy[4] {0, 0, -1, 1}; void dfs(int x, int y, int step) { // 剪枝当前步数已经超过历史最少步数就没必要继续了 if (step minSteps) { return; } // 到达终点 if (x N - 1 y M - 1) { pathCount; if (step minSteps) { minSteps step; } return; } // 尝试四个方向 for (int i 0; i 4; i) { int nx x dx[i]; int ny y dy[i]; // 边界判断 if (nx 0 || nx N || ny 0 || ny M) { continue; } // 墙判断 if (maze[nx][ny] 1) { continue; } // 已访问判断 if (visited[nx][ny]) { continue; } visited[nx][ny] 1; dfs(nx, ny, step 1); visited[nx][ny] 0; // 回溯撤销标记允许其他路径经过 } } int main() { visited[0][0] 1; // 起点标记为已访问 dfs(0, 0, 0); printf(总路径数: %d\n, pathCount); printf(最短步数: %d\n, minSteps); return 0; }4.3 逐段拆解代码里的每个细节都在解决什么问题我们拆几个最容易写错的位置。方向数组的作用。dx和dy是对应关系dx[0]-1, dy[0]0表示向上走一步。方向数组选固定的方向顺序上、下、左、右不一定是最优的但能保证输出序列的确定性。它在迷宫、BFS、图遍历里是标配建议直接背下来。**if (step minSteps) 这个剪枝。**你仔细看这一句其实不是必需的——没有它程序一样能跑出所有路径和最短步数只是会非常慢。它的含义是如果已经走了超过当前已知最短的步数还没到终点那这条路就算走到底也不可能更短了直接放弃。这种剪枝叫最优化剪枝在最短路径问题里作用极大。对n很大的迷宫没有它可能就是指数级的爆炸有了它往往能指数级收敛。visited 的标记与撤销为什么都必要。visited[nx][ny] 1是防止在一条路径里反复走同一个格子否则会无限递归。visited[nx][ny] 0是让其他路径可以经过这个格子。这两个缺一不可。如果你只标记不撤销那只能找到第一条路其他所有路径都断了如果你撤销但没标记那程序会在两个格子之间来回跳到栈溢出。步数为什么用参数传递而不是全局变量。step是递归参数天然每层一个副本。当你回溯到上一层时step自动恢复成上层的值。如果设成全局变量你就得自己想着进去之前加1出来之后减1非常容易出错。这里推荐一条经验能往参数传的就不要用全局变量全局变量越少回溯时脑子越清醒。minSteps这种必须全局比较的值才用全局变量。**边界判断为什么要写在递归函数里面而不是外面。**理论上你可以在调用dfs(nx, ny)之前就判断nx、ny是否越界、是不是墙但通常更省事、更不易漏的做法是在函数入口统一校验。C语言里越界访问数组是未定义行为轻则值错乱重则段错误。所以边界判断建议放在所有访问数组之前。5. DFS的进阶关键剪枝策略、重复状态处理与记忆化很多偏难的DFS题难点根本不在DFS本身而是怎么在DFS的搜索过程中避免做无用功。这一节是真正区分会写DFS和能用DFS刷题的分水岭。5.1 三种最常见的剪枝手段剪枝的思路一句话总结在进入某个递归分支之前提前判断这个分支不可能产生合法解或最优解直接跳过。第一种可行性剪枝。最经典的是在组合总和问题里如果当前累加和加上剩余最小元素都超过目标值那后面没必要再试了。例如LeetCode 39的组合总和你先排序然后求和超过target直接return。第二种最优化剪枝。这是迷宫代码里用的那种——如果当前路径长度已经不小于已知最优解就没必要继续探索。在很多最小步数最少操作次数类题目里都会用到。第三种重复状态剪枝。这在状态搜索类题目里特别重要。例如在单词搜索里同一个位置的字母不能重复使用就需要visited数组去记录而在跳跃游戏里你可能发现访问到某个位置时剩余的步数已经不比上次访问它时多那这条路根本不需要再走可以直接剪掉。严格说这已经属于记忆化搜索了——把某个状态的最优值存下来遇到重复状态直接复用而不是重新搜一遍。5.2 记忆化搜索DFS与动态规划的交界地带记忆化搜索严格来说不是DFS但它建立在DFS之上。思路是如果搜索树里大量出现重复的状态并且这些状态的最优值是确定的那么第一次算出之后用数组或哈希表存下来后续再遇到就直接返回缓存值不去重复递归。举例经典问题登山问题也可以理解成科罗拉多州的山脉最长递增路径给定一个二维数组求最长的严格递增路径长度。裸DFS会反复计算同一个点出发的最长路径非常浪费。加一个memo[i][j]缓存每个点最多计算一次复杂度从指数级直接降到O(N×M)。int memo[4][4] {0}; // -1表示未计算初始化为0配合长度最小为1也可用-1 int dfs(int x, int y) { if (memo[x][y] ! -1) { return memo[x][y]; } int maxLen 1; for (int d 0; d 4; d) { int nx x dx[d]; int ny y dy[d]; if (nx 0 || nx N || ny 0 || ny M) continue; if (maze[nx][ny] maze[x][y]) continue; int len 1 dfs(nx, ny); if (len maxLen) maxLen len; } memo[x][y] maxLen; return maxLen; }这种DFS 缓存的写法已经非常接近动态规划了。区别只是先递归到小规模状态再逐层返回从形式上是自顶向下而DP是自底向上迭代。理解DFS到记忆化这条路径对之后学动态规划极其有利。5.3 DFS与BFS的边界和取舍DFS不是万能的。这里说一个关键场景求最短路径的时候BFS往往优于DFS前提是无权图。原因很简单BFS一层一层向外扩展第一次到达终点所在的层数就是最短层数而DFS的最短是在所有路径都走完的基础上比较出来的指数级搜索和剪枝比拼通常BFS更快。那DFS还有何用求所有路径、所有方案比如所有排列、所有子集时DFS天然适合。求可达性、连通块数量时DFS简单好写。在状态空间太大、不适合BFS一层层展开时DFS配合剪枝往往更灵活。再说一个高频面试题DFS和BFS的区别怎么答。其实就抓一点DFS用栈递归隐式用栈BFS用队列DFS是一条路走到黑BFS是同心圆式扩张DFS适合方案枚举BFS适合最短路径。5.4 常见的DFS错误模式清单我在帮人改代码过程中见过太多重复的错误汇总成一份清单直接对着排查错误表现可能原因解决办法递归无限循环、栈溢出缺少visited标记或标记条件写错在递归入口先判断并标记确保不会回访输出结果漏项终止条件过严提前return检查终止条件确定是depth n还是depth n答案重复同一层for循环里对相同数值重复选择先排序跳过与前一个相同且未使用的元素结果正确但超时缺少剪枝排序 最优化/可行性剪枝结果莫名错乱visited撤销位置不对确保visited[i] 0紧跟递归返回之后不要挪到for循环外面返回结果被覆盖把结果集存成了全局指针递归改动影响历史结果把结果拷贝到新容器/新数组再存6. 给偏难党的最终建议三个阶段的刻意练习路线很多人问DFS到底要刷多少题才能掌握我给不出具体数字因为质量比数量重要得多。但练习路线是清晰的按三个阶段走基本能把这个偏难变成必拿分。6.1 第一阶段只做三类基础题精做而不是刷量我推荐从这三类题入手每题至少自己完整写三遍第一遍对着代码抄并加注释第二遍关掉参考自己写第三遍把代码手推到每个递归分支都能在脑子里跑通。全排列、子集、组合这一组是DFS的Hello World务必理解到滚瓜烂熟。岛屿数量、迷宫寻路掌握二维矩阵上的DFS套路包括visited标记、方向数组、边界判断。括号生成、电话号码字母组合这些是字符串DFS的代表能训练在递归过程中构建结果字符串的能力。6.2 第二阶段开始正面刚剪枝和记忆化当基础题能做到看到题目就知道用DFS之后开始做需要剪枝的题。这个阶段的目标不是求对而是对比不剪枝和剪枝的耗时差距加深对剪枝价值的理解。我在这个阶段做过一个组合总和的超时版本当时跑一个测试用例用了3秒多加上排序和剪枝后变成10毫秒以内那个对比直接让我对剪枝有了肌肉记忆。这一阶段也可以开始触碰记忆化搜索的题目比如最长递增路径、打家劫舍III树形DP但可以用DFS。学会先写暴力递归再加缓存两步走很多DP题你其实已经会做了一半。6.3 第三阶段拿真题实战刻意限制时间当你的工具库里有了DFS 剪枝 记忆化 回溯你已经能和很多偏难题正面交手了。第三阶段的目标是在限定时间内稳定输出。我习惯用这个方法拿到一道陌生题先用3分钟判断这题是不是DFS——看到所有可能路径所有方案是否存在一条路径连通块数量这些字眼大概率就是DFS看到最短步数最少操作次数且有明确的一层一层扩张感优先考虑BFS看到状态重复且最优性依赖子问题就往记忆化/DP方向想。判断出来之后先写框架递归函数参数、终止条件、for循环遍历选择、标记/撤销。这个框架一旦跑通剩下的就是调细节。初期可以超时但分析超时原因时一定要往能不能剪枝上想而不是盲目加缓存。6.4 我在实际调试中的一个小技巧最后送你一个屡试不爽的调试技巧在递归函数入口打印当时的入参和当前状态。很多人觉得调试递归太麻烦其实只要在入口加一行printf(enter dfs: x%d, y%d, step%d\n, x, y, step)你会瞬间看清楚整个搜索到底走了哪些路、在哪个分支返回、为什么结果是这样。我当年学DFS最崩溃的一次是写迷宫路径数时老是比答案多出来几倍。加了一行打印之后才发现原来我少了已访问判断导致路径在相邻两个格子之间来回走。这行打印比我在纸上演算两个小时都管用。说实话DFS偏难这个印象很大程度是递归的执行模型和普通循环代码差别太大导致的。一旦你在纸上、在调试器里真正看明白一次压栈弹栈的全过程后面的回溯、剪枝、记忆化全都是一马平川。希望这篇能帮你捅破那层窗户纸而不是继续对着模板背到怀疑人生。