1. DFS到底是什么不撞南墙不回头的遍历思维很多刚接触算法竞赛的朋友第一次在题解里看到DFSDepth First Search深度优先搜索时脑子里其实是懵的。搜索搜什么是从一堆数据里找一个目标吗还是像搜索引擎那样去查资料都不是。我一直觉得DFS与其说是一种算法不如说是一套穷举的思维框架。它的核心逻辑只有一句话沿着一条路走到黑走不通了再退回来换一条路继续走直到把所有可能的路都走完。打个最朴素的比方。你在一个迷宫里找出口DFS的走法是这样的随便挑一面墙贴着走一直走到死胡同然后退回到刚才的分岔路口换另一个方向继续走。这跟BFS宽度优先搜索那种一层一层往外扩散的策略完全不同DFS的性格更莽但它能保证只要迷宫有出口你最终一定能找到。在算法竞赛里DFS最常用的场景是解决决策型问题。什么叫决策型问题就是你在每一步都要做一个选择每个选择都会产生新的分支最后需要在这些分支组成的选择树里找到满足条件的答案。比如从一个数字集合里选几个数使它们的和等于某个目标值在有障碍物的网格里从起点走到终点有多少条不同路径给N个物品每个选或不选求最大价值。这类问题用暴力循环写要么嵌套层数不确定要么代码写到你怀疑人生。但用DFS一套递归代码就能把整棵选择树完整地走一遍无非就是选这个分支走到底不行再回来选另一个。算法竞赛里的DFS本质上就是用递归的方式实现一场系统性的、不重不漏的路径遍历。不重是指同一条路径不会走两遍不漏是指所有可能的路径都被考虑过。这四个字是整套DFS代码正确性的根基后文所有代码都会围绕这一点展开。提示如果你完全没接触过递归先别慌。DFS的代码骨架里递归占比很高但它的思路比代码本身简单得多。我建议你先理解走到尽头就回头这句话再看代码会轻松很多。2. 递归DFS的代码载体与执行真相2.1 从调自己开始理解递归调用栈DFS通常用递归实现因为递归函数天然适合描述深入下一步的过程。很多初学者在看递归代码时脑子里会想象函数不停复制自己、自我嵌套其实这个理解是反的——真正发生的是同一个函数被反复调用每次调用都有自己的独立变量空间它们在内存里按顺序压入调用栈。我们来看一个最经典的入门例子输出1到N的全排列。这个题几乎每本算法书都有蓝桥杯、PAT、力扣的Top题库里也都有它的变体值得彻底吃透。#include bits/stdc.h using namespace std; int n; // 要排列的数字个数 int path[10]; // 记录当前排列 bool used[10]; // used[x] true 表示数字x已经被用过 void dfs(int step) { // step 表示当前要填第几个位置 if (step n) { // 1. 所有位置都填完了输出结果 for (int i 1; i n; i) { cout path[i] ; } cout endl; return; // 2. 回到上一层调用 } for (int x 1; x n; x) { // 3. 枚举所有数字 if (!used[x]) { // 4. 如果这个数字还没用过 path[step] x; // 5. 在当前层直接赋值 used[x] true; // 6. 标记为已用 dfs(step 1); // 7. 递归填下一个位置 used[x] false; // 8. 回溯撤销标记尝试下一个数字 } } } int main() { cin n; dfs(1); // 从第一个位置开始 return 0; }这段代码只有两个关键动作标记和撤销标记。每次进入一个新的dfs(step)就是在填第step个位置这个节点上做选择递归调用dfs(step 1)则是往下一层推进当step n时说明一条完整的排列已经构造完输出并return。2.2 调用栈的可视化排列3个数时到底发生了什么很多人看代码能看懂但一追问计算机是怎么一层层往上返回的就卡住了。我建议你亲手画一张调用栈图。以n3为例当程序执行到dfs(3)内部的dfs(4)时调用栈从上到下大致是这样的dfs(4) - step4满足step3输出path[1..3]return dfs(3) - 正在执行 for 循环等着 dfs(4) 返回 dfs(2) - 正在等待 dfs(3) 返回 dfs(1) - 正在等待 dfs(2) 返回 main - 正在等待 dfs(1) 返回每个dfs(step)调用在执行完自己的for循环后会自然结束然后控制权交还给上一层调用继续执行上一层自己还没跑完的for循环。这个过程就是回溯的底层机制——不是代码跳来跳去而是栈出栈的天然行为。我见过太多新手在if (step n)的return之后忘记处理used[x]的复位。结果就是排列数量骤减或者出现1 1 1这种明显错误的输出。因为数字1一旦被标记在整个递归深入过程中都不会被再次使用等到回溯回来时如果你不撤销后面的位置就几乎无数字可用了。这套标记-递归-撤销的模式掌握之后会发现是高度套路的。你甚至不需要背代码只需要理解每一步在做什么然后对着题目套骨架。我自己的习惯是凡是碰到枚举所有选择、每种选择还要影响后续选择的题目第一反应就是DFS。3. 回溯的本质状态撤销与现场还原3.1 什么叫回溯为什么必须撤销状态上一节的全排列代码里used[x] false那一行就是回溯。为什么要撤销因为同一套标记状态需要被不同分支复用。举个例子。你已经选了1、2作为前两个数字递归调用进入第三层填了3输出了1 2 3然后返回。此刻如果你不把3的标记撤销那么回到第二层、尝试下一轮循环时数字3还是已用状态但第二层此时明明还没有选3这是个错误的现场。只有撤销标记第二层才能正确地在选了1、2这个现场下接着尝试把3放到别的可选位置。回溯这个概念如果抽象成一句话就是在递归返回后要把本次选择造成的影响全部消除让程序回到还没做这个选择的状态。很多初学者一开始对撤销不太重视觉得反正答案对了就行。但一旦遇到N皇后、数独、图的路径枚举这类问题状态种类变多棋盘标记、位置标记、剩余数字表、方向数组访问标记漏掉一次还原就会产生灾难性的连锁错误而且错误往往是隐蔽的——可能在某个分支上才出现其余分支一切正常。这种bug在竞赛中是出了名的难debug。3.2 迷宫寻路用DFS走通带障碍的地图全排列是DFS最简单的载体因为选择空间是一维的选哪个数字。实际竞赛里更常见的是二维甚至多维空间搜索比如迷宫。来看一个经典迷宫问题给定一个n*m的地图1表示障碍0表示空地从(1,1)出发问能否走到(n,m)如果能最少步数是多少BFS求步数DFS求可达性和路径。DFS负责找路的核心代码长这样const int dx[] {-1, 1, 0, 0}; const int dy[] {0, 0, -1, 1}; int n, m; int maze[105][105]; bool visited[105][105]; bool dfsMaze(int x, int y) { if (x n y m) return true; // 到达终点 visited[x][y] true; // 标记当前点已访问 for (int k 0; k 4; k) { // 枚举四个方向 int nx x dx[k]; int ny y dy[k]; if (nx 1 || nx n || ny 1 || ny m) continue; // 越界跳过 if (maze[nx][ny] 1) continue; // 撞墙跳过 if (visited[nx][ny]) continue; // 已经走过跳过 if (dfsMaze(nx, ny)) return true; // 深入找到就直接返回 } return false; // 四个方向都走不通 }这段代码里有个很重要的细节需要强调递归调用之前检查visited递归内部立刻设置visited[x][y] true而不是在for循环里临时判断标记。为什么因为visited的作用是防止在一条路径上绕圈子我们是用全局标记配合递归实现的。如果把标记放在for循环内且不还原你可能会错过从其他路径合法地访问同一个点。对于只问是否存在路径的问题visited标记可以不撤销因为一旦某个点在当前搜索路径中被访问过再通过别的路径走到它接下来的所有可能结果都已经在第一次访问时探索过了重复访问只会浪费时间。但如果你要的是所有路径或者所有排列visited/used就必须撤销因为每个分支需要看到不同的历史状态。这里有一个非常容易混淆的点我建议你在做题时先问自己一句这题是求第一组解、所有解的数量还是最优解不同目标决定visited撤销与否、DFS要不要剪枝、甚至该不该用DFS。先想清楚求解目标再动键盘比闷头写代码高效得多。4. DFS的经典应用场景从排列组合到图与连通块4.1 排列组合竞赛里最频繁出现的DFS模板全排列讲过了排列衍生出的组合问题在竞赛里几乎每周都见。比如从{1, 2, 3, ..., n}里选k个数打印所有组合。组合与排列的关键区别是组合不在乎顺序1 2 3和3 2 1是同一种。DFS写组合时有一个经典优化强制让选择顺序递增。也就是在递归参数里加一个startIndex每次只从startIndex之后选数。这个设计直接把搜索空间砍掉一半以上还天然避免了重复集合的产生。int n, k; int comb[25]; void dfsCombine(int step, int start) { if (step k) { // 选够了k个数 for (int i 1; i k; i) cout comb[i] ; cout endl; return; } for (int i start; i n; i) { // 只从start开始枚举 comb[step] i; dfsCombine(step 1, i 1); // 下一个数必须比当前大 } }这段代码的变化只有一个参数start但效果立竿见影。没有start时你要额外判断当前组合是否已经出现过有了start之后1 2 3只会在第一个数是1、第二个数是2、第三个数是3时被构造一次绝不会出现3 2 1。这种通过参数约束搜索顺序的思路在DFS题目里是一种通用优化手段值得反复体会。4.2 图的DFS遍历邻接表与连通块计数DFS另一个高频场景是图论。判断一个无向图有多少个连通块、判断两个点是否连通、拓扑排序的DFS实现、找桥找割点全都绕不开DFS。以连通块计数为例核心代码只有十几行vectorint g[1005]; bool vis[1005]; void dfsGraph(int u) { vis[u] true; for (int v : g[u]) { if (!vis[v]) dfsGraph(v); } } int countComponents(int n) { int cnt 0; for (int i 1; i n; i) { if (!vis[i]) { cnt; // 发现一个新的连通块 dfsGraph(i); // 把这个块内所有点都标记 } } return cnt; }为什么dfsGraph(i)一次能标记一个连通块的全部点因为DFS的递归特性是一旦进入一个点就会不回头地把所有能到达的点走完。这种从某个起点出发、尽力扩散的行为正好和一个连通块的定义完全吻合块内任意两点之间都有路径块与块之间没有路径。vis数组在这里同样不需要撤销。理由跟上文说的一样图的遍历目标是把每个点至少访问一次不需要回退去枚举不同路径的排列。掌握这个DFS遍历图visited只加不减的模型后面学tarjan、割点、缩点会顺很多。4.3 网格类问题从岛屿数量到洪水填充刷过力扣或者蓝桥杯的朋友一定见过岛屿数量这道题一个二维网格1是陆地0是海水问有多少个岛屿。解法思路跟图连通块几乎一模一样差别只是把vector邻接表换成了四个方向的网格移动。void dfsGrid(int x, int y, vectorvectorchar grid) { if (x 0 || x grid.size() || y 0 || y grid[0].size()) return; if (grid[x][y] 0) return; grid[x][y] 0; // 直接在原地图上沉没岛屿 dfsGrid(x 1, y, grid); dfsGrid(x - 1, y, grid); dfsGrid(x, y 1, grid); dfsGrid(x, y - 1, grid); }这段代码有一个非常实用的小技巧直接把访问过的陆地改成海水grid[x][y] 0省掉了一个额外的visited数组。这在竞赛和面试里都能用能少维护一个数据结构代码也更简洁。前提是确定可以原地修改地图如果地图后续还要用就不能这么干得另开visited数组。如果题目从数岛屿升级成最大岛屿面积思路一模一样只是把dfsGrid的返回值变成int每次扩展时累加面积即可。这类在一个网格上沿着四方向/八方向搜索连通区域的模型就是洪水填充算法Flood Fill很多和图像处理、地图模拟相关的题目都会在它上面做文章。5. 剪枝的艺术DFS性能差距的关键5.1 什么情况需要剪枝无脑DFS的代价DFS的问题也很明显如果搜索树又大又深纯靠递归硬跑状态数量会爆炸。你可能会遇到一个n25的排列题暴力枚举25!种情况计算机跑一年也跑不完。这时候就必须引入剪枝——在递归开始深入之前提前判断这条分支是否还有希望如果注定无解或不是最优立刻放弃这条路径不再往下走。剪枝不是优化是唯救命稻草。竞赛里常见的剪枝策略有这么几类可行性剪枝当前状态已经违反约束比如拿到的数已经超过目标和再往下加只会更大直接return最优性剪枝当前累计的值已经比已找到的最优解差了不适合用来做是否超过当前最优判断的直接return顺序优化先搜索更容易产生解的分支比如按数字从大到小搜索往往能更快逼近最优解从而给最优性剪枝提供更紧的上界。对称性剪枝在某些组合问题中交换两个相同物品无意义可以强制搜索顺序减少重复。5.2 一个经典的剪枝案例N皇后问题N皇后问题应该算是DFS剪枝最经典的考题了。在n*n的棋盘上放n个皇后要求任意两个皇后不在同一行、同一列、同一对角线。这题如果用纯暴力枚举所有摆放方式复杂度是O(n^2的n次方)级别的n稍大就崩。DFS解法是逐行摆放每一行尝试放一列用三个布尔数组记录哪些列、哪些主对角线、哪些副对角线已经被占用然后递归到下一行。当我发现某一行所有列都被占用时这层递归的for循环自动结束相当于天然剪枝。核心代码如下bool col[15], diag1[30], diag2[30]; int ans 0, n; void dfsQueen(int row) { if (row n) { ans; return; } for (int c 0; c n; c) { if (col[c] || diag1[row c] || diag2[row - c n]) continue; col[c] diag1[row c] diag2[row - c n] true; dfsQueen(row 1); col[c] diag1[row c] diag2[row - c n] false; } }这里用了一个数组下标技巧主对角线上所有点的row - c值相等副对角线上所有点的row c值相等。为了避免row - c出现负数统一加n偏移量。这样判断对角线是否冲突时间复杂度直接O(1)。类似的索引压缩技巧在棋盘类和矩阵类DFS中非常常见熟练掌握能省不少事。当n8时这个代码在普通家用电脑上运行的时间接近瞬间完成但如果你不使用任何剪枝纯暴力枚举所有棋盘摆放复杂度是不可想象的。剪枝的本质就是利用题目约束条件把搜索空间从全部可能压缩到真正有意义的那一小部分。6. DFS实测经验常见坑与排查思路6.1 递归深度栈溢出是初学者最常见的翻车原因DFS依赖系统调用栈每一层递归都要占用栈空间。默认8MB的栈大概能支持的递归层数在几千到几万层之间跟栈帧大小有关。但有些题目地图很大比如1000x1000的网格洪水填充递归深度可能达到十万层以上直接Stack Overflow。遇到这种情况要么把递归DFS改成显式栈模拟stackpairint, int st; st.push({sx, sy}); while (!st.empty()) { auto [x, y] st.top(); st.pop(); // 处理当前节点把相邻未访问节点压栈 }要么在比赛前用编译器指令加大栈空间GCC在Linux下可加-Wl,--stack,268435456。我还见过有人把显式栈当DFS用结果因为pop顺序跟递归不一致导致输出路径和预期不同——那是因为栈先入后出往栈里push邻居的顺序决定了实际搜索的遍历顺序。如果你想严格复现递归DFS的访问顺序可以考虑用vector模拟栈并手动控制栈顶指针这样顺序就完全一致了。6.2 忘写visited导致死循环第二个高频坑是漏掉visited标记或者标记写错位置。尤其在网格搜索和图搜索里如果你不标记这个点已经访问过DFS会在这条路径上反复横跳从A走到BB又走回AA又走到B……直到栈溢出或者TLE。正确的做法是在进入某个点的那一刻就标记而不是在准备进入时才标记。如果你在if判断里才标记可能出现多个分支同时尝试进入同一个点的问题。如果题解要求所有路径那visited标记要在递归返回时撤销如果要求的是连通性、是否存在路径那visited标记永不撤销省时省力。6.3 参数传递顺序与全局变量污染很多人在写DFS时习惯把所有变量都设成全局方便省事。但全局变量有个致命问题整个递归过程中所有分支共享同一份状态。一旦某个分支忘还原状态其他分支就会拿到被污染的数据。我自己早期写DFS时经常因为少还原一个cnt计数器排错排一个晚上。一个比较稳妥的做法是把状态变量作为递归参数传递或者严格遵循谁修改、谁还原的原则在每一层递归前和后成对地修改/还原。针对计数这类状态我建议用返回值累加的方式代替全局计数器能少很多麻烦。还有一个小技巧如果题目分多个测试数据记得在每组数据开始前重置所有全局状态数组。这个看似基础的操作在蓝桥杯的填空题里坑过很多人——因为前一组测试的DFS已经把标记数组改了忘了重置第二组数据从第一分钟起就是错的。7. DFS下一步学什么从入门到国奖的进阶路线DFS本身是一个极其基础又极其百搭的算法。掌握了最朴素的递归回溯框架后我建议你按这个顺序继续往下走每一步都以能做出一类题为目标而不是读完就算BFS宽度优先搜索和DFS刚好相对。DFS走一条路走到黑BFS一层一层扩散。最短路径、最少步数、状态转移等问题基本都是BFS的主场。推荐做力扣的二叉树层序遍历打开转盘锁。回溯法在排列组合中的应用把全排列和组合的代码吃透后做力扣的组合总和子集复原IP地址这些题。它们都是同一个模板的不同变体。记忆化搜索当DFS过程中存在大量重复子问题时用dp数组缓存中间结果就是记忆化搜索。比如斐波那契数列、滑雪问题、数位DP的许多题都用这个技巧。剪枝策略的系统学习从N皇后开始逐步理解可行性剪枝、最优性剪枝、排序剪枝的应用场景。竞赛里很多DFS题卡的其实不是思路而是剪枝优化这一步跨过去才能从会写DFS变成会用DFS。DFS在图论算法中的延伸连通分量、割点、桥、强连通分量、拓扑排序的DFS版本都是DFS和图论的深度结合。蓝桥杯国赛里经常出现这类题。如果你正在准备蓝桥杯或ACM我个人强烈建议把DFS当成第一个认真吃透的算法。因为它能覆盖大批基础题同时又是后续图论、树形DP、状态压缩的预修课。算法竞赛里很多高分选手都是把DFS写到了条件反射的程度——看见枚举所有情况就能立刻手写DFS骨架看见求最短步数立刻切BFS思维。这种肌肉记忆的建立没有捷径就是靠刷题量的堆积。刚开始哪怕一天只做一两道DFS题也没关系坚持一个月你会明显感觉到递归思路顺畅了一大截。最后分享一个我自己的习惯每次写DFS题之前先在纸上画出搜索树的形态标清楚哪些节点需要回溯哪些不需要哪些分支可以剪掉剪的依据是什么。这个习惯十分钟就能养成但它能省下大量debug时间也让你的DFS代码从一开始就是结构清晰的而不是写到哪想到哪。算法竞赛这条路没有太多神秘的东西就是一遍遍地把基础动作练到极致DFS就是那个值得一开始就投入时间的基本功。