提到“搜索”大家第一反应往往是搜索引擎、关键字命中的东西。但在算法领域“搜索”这个词要朴素得多给你一个起点在有限的或者近乎无限的状态空间里找到目标。而深度优先搜索Depth First SearchDFS就是所有搜索策略里最直白的一种——选定一条路走到黑走不通就退回最近的分岔口换一条。这篇文章围绕“搜索之DFS”展开我会把DFS的原理、递归实现、遍历顺序、图上的应用、回溯与剪枝以及我实际写代码时踩过的坑一次性梳理清楚。无论你是准备面试、刷题还是项目里要遍历某棵树、某张网、某个状态空间这篇文章都值得你从头看到尾。1. 为什么说DFS是所有搜索算法的地基1.1 一个迷宫问题引出的核心选择假设你站在一个迷宫入口手里没有地图。最简单的策略是什么先选一堵墙贴着一直往前走遇到死胡同就返回上一个岔路口换一个方向继续试。这不是什么高深技巧这就是深度优先搜索的原始形态。计算机里的DFS和人类的迷宫直觉完全一致优先往深处探索把“当前路径”推到极限直到无法继续前进再回溯到最近的决策点。和它形成对照的是广度优先搜索BFS。BFS像“一圈一圈往外扩散”从一个点出发先看所有相邻点再看所有相邻点的相邻点。迷宫场景里BFS相当于你在入口处同时派出很多只蚂蚁每只蚂蚁同时走一步谁先碰到出口谁就是最短路径。DFS不保证最短路径它更关心“能不能找到一条路”以及“把整个空间逛完需要怎么走”。这个差异非常重要。很多新手刚接触DFS时会困惑为什么同样的图DFS能遍历所有节点BFS也能遍历所有节点但路径结果不一样因为两者的“推进策略”不同。DFS维护的是一个后进先出的栈结构走进去的路径越深越先被展开BFS维护的是一个先进先出的队列离起点越近的点越先被展开。栈和队列这两种最基本的数据结构几乎就是DFS与BFS的全部区别。1.2 搜索之DFS的适用边界什么时候“深挖”优于“广播”既然DFS不保证最短路径那它在实际中到底能干什么我总结成三类第一存在性判断比如“这个图是否连通”“迷宫里从A能不能走到B”“这个棋盘是否存在一组解”第二结构枚举比如“列出所有可能的全排列”“找出二叉树的所有路径”第三空间遍历比如“把一个图的所有节点完整地过一遍顺便记录路径先后关系”。与之相对如果问题是“从A到B的最短路径是几步”那就应该选BFS如果问题是“每一步都带权求最小花费”那应该去学Dijkstra如果问题是“状态太多但每个状态只会被解锁一次”那可能还要考虑动态规划。DFS的舒适区在于解空间天然是树状或图状的我们要么找一个解要么找所有解而不是找一个“最优解”。维度DFSBFS核心结构栈递归时是系统调用栈队列路径保证不保证最短路径无权图下保证最短路径空间复杂度树高级别的栈空间往往更省层级宽度可能爆炸典型用途连通性、回溯枚举、环检测最短步数、层级扩散实现难度递归极简迭代稍绕迭代直观递归少见从这张对比表能看出DFS的空间表现通常比BFS好因为一棵树的宽度往往远大于深度。这也是为什么很多图论算法框架里DFS被用作基础遍历器。你可以在DFS上做拓扑排序、强连通分量、割点检测、欧拉回路这些算法如果改用BFS实现会别扭得多。搜索之DFS看起来只是“一条路走到黑”但它其实是整个图算法体系里最重要的一块基石。2. DFS的底层运行机制递归栈与手动栈2.1 递归调用栈递归DFS的隐形数据结构第一次接触DFS的人往往会被递归绕晕函数怎么能在没执行完的时候调用自己关键在于“每次调用都会创建一个新的执行上下文”。在现代编程语言里每个正在运行的函数都会占用一段系统栈空间栈里存它的参数、局部变量、返回地址。当函数A调用函数B时A的上下文被压在栈底B的上下文在栈顶B返回后A继续执行。递归不过是函数调用了自己系统栈里会连续压入多层相同的函数上下文。这句话可以记一辈子递归DFS不需要你手动声明栈系统调用栈已经替你干了这件事。看一个简单的二叉树遍历代码def dfs(node): if node is None: return print(node.val) # 进入节点时做的事 dfs(node.left) # 深入左子树 dfs(node.right) # 深入右子树当dfs进入左子树时父节点的状态包括当前节点引用就静静地躺在栈里。左子树全部遍历完函数返回父节点接着执行下一行。这种“自动保存现场”的能力是递归处理深度优先搜索的天然优势。手动栈迭代版本反而需要你自己把“还没做完的事”压进栈里。2.2 为什么有时候要把递归改成手动栈递归版本写起来爽但有一个致命弱点递归深度受系统栈限制。Python默认递归深度大约在1000层Java和C会稍微高一些但也经不起极端情况。你拿递归DFS处理一条链表形状的树比如数据量很大的二叉搜索树退化成链表几百层可能没问题几千层直接RecursionError或者StackOverflowError。这时候就需要手动栈。以二叉树前序遍历为例递归版本如上迭代版本长这样def preorder_iterative(root): if root is None: return [] res [] stack [root] while stack: node stack.pop() res.append(node.val) # 注意压栈顺序因为栈是后进先出先压右孩子再压左孩子 if node.right: stack.append(node.right) if node.left: stack.append(node.left) return res手动栈版本里最容易出错的地方就是压栈顺序。你想让左孩子先被访问但栈是后进先出所以必须先把右孩子压进去再把左孩子压进去这样下一次循环弹出来的是左孩子。别看这是个很小的细节我在面试别人时超过一半的候选人在手动栈遍历上栽在这里。什么时候值得换成手动栈我自己的经验是递归写法在数据规模安全的前提下永远优先因为可读性最好一旦遇到可能深达上万层的图或树或者递归里需要记录额外的路径状态导致栈帧很重立刻改手动栈。也可以写两者对比的版本先用递归跑通逻辑再改成迭代应对大输入。def dfs_iterative(graph, start): visited set() stack [start] while stack: node stack.pop() if node in visited: continue visited.add(node) # 处理当前节点 for neighbor in reversed(graph[node]): if neighbor not in visited: stack.append(neighbor) return visitedreversed在这里不是必须的但它能保证节点被访问的顺序和递归版本基本一致。调试递归和迭代版本时最省事的手段就是打印每个节点的进出栈时间肉眼比对两次遍历顺序是否完全一致。3. 二叉树里的DFS三种顺序的选择逻辑3.1 前序、中序、后序各自解决什么问题树的DFS天然有三种节奏先处理当前节点再深入子树叫前序先序先深入左子树再处理当前节点再深入右子树叫中序先处理完左右子树再处理当前节点叫后序。这三种顺序分别解决不同类型的问题不能混用。前序遍历的场景序列化一棵树、复制一棵树、寻找根到叶子的路径。因为这些操作希望在“还没有深入子节点之前”就把当前节点的信息记录下来。中序遍历最经典的场景是二叉搜索树中序遍历一棵二叉搜索树得到的序列一定是升序的。如果你要校验一棵树是不是合法的二叉搜索树或者把一棵二叉搜索树转成有序链表中序是不二之选。后序遍历则是“先知道子树的结果再决定父节点怎么算”的场景计算树的高度、统计某个子树内满足条件的节点数、删除一棵树的所有节点。后序的核心是“子树结果合并”。我举个例子计算二叉树的最大深度def max_depth(root): if root is None: return 0 left_depth max_depth(root.left) right_depth max_depth(root.right) return max(left_depth, right_depth) 1这个递归必须用后序逻辑因为当前节点的高度取决于左右子树的高度你得先拿到两个子树的返回值。如果硬写成前序“先算当前节点”就会发现根本拿不到子树的深度。3.2 从树的DFS到通用状态搜索的抽象树是一种非常特殊的图没有环每个节点只有一个父亲。因此树的DFS不需要记录“是否访问过”因为天然不会走回父节点。但真实的图搜索必须记录访问状态否则会死循环。从树的DFS抽象出来的其实是三段式结构状态进入、中间处理、状态恢复。def dfs_template(node, state): # 第一阶段进入节点前的判断与状态记录 if node is None or invalid(state): return # 第二阶段在当前节点做决策 state.append(node) # 第三阶段递归深入邻居 for neighbor in node.neighbors: dfs_template(neighbor, state) # 第四阶段离开节点时撤销状态 state.pop()这个模板就是后面回溯法的雏形。很多新手写DFS只记“递归 访问”忘掉“离开前撤销状态”结果在枚举类题目里输出一堆重复结果。理解树的DFS只是这个模板的特例树的遍历不需要访问标记也不需要撤销状态因为二叉树节点只被单向路径访问不存在其他分支共用同一个状态的场景。一旦跳到图上、棋盘上、状态空间里模板的第三和第四阶段就必须老老实实写出来。4. 图的搜索与通用框架连通性、路径与环4.1 图DFS的标准模板与visited的关键性图的DFS和树的DFS唯一的本质区别就是“有没有访问标记”。树不会回环图会。无向图里A访问BB又访问A如果没有标记DFS会无限振荡。无向图的标准做法是用一个visited集合或数组只要节点被访问过就不再进入。def dfs_graph(graph, start): visited set() def dfs(node): visited.add(node) print(fenter: {node}) for neighbor in graph.get(node, []): if neighbor not in visited: dfs(neighbor) print(fexit: {node}) dfs(start)有向图里除了visited还有一种更精细的三色标记法专门用来检测环。白色表示还没被访问灰色表示正在递归栈中黑色表示已经遍历完成。如果在DFS过程中遇到了一个灰色节点就说明出现了环。这个技巧在课程选修顺序、任务调度等场景里非常常用。WHITE, GRAY, BLACK 0, 1, 2 def has_cycle(n, graph): color [WHITE] * n def dfs(u): color[u] GRAY for v in graph[u]: if color[v] GRAY: return True if color[v] WHITE and dfs(v): return True color[u] BLACK return False for i in range(n): if color[i] WHITE and dfs(i): return True return False三色标记法比简单的visited多提供了一个维度的信息它不仅能告诉你“这个节点访问过没有”还能告诉你“它是否还在当前的调用链上”。凡是跟依赖关系、先后关系有关的问题灰色状态都是最关键的指标。4.2 网格类DFS把矩阵当成图来处理在实际项目中图不一定以邻接表形式存在。最常见也最容易诱导新手犯错的是网格矩阵。比如一个m x n的二维矩阵每个格子是一个节点上下左右相邻的格子之间有边。处理这种问题最自然的DFS写法是四个方向递归def num_islands(grid): if not grid: return 0 m, n len(grid), len(grid[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(i 1, j) dfs(i - 1, j) dfs(i, j 1) dfs(i, j - 1) count 0 for i in range(m): for j in range(n): if grid[i][j] 1: count 1 dfs(i, j) return count这里的核心技巧是不额外开visited数组而是直接把访问过的陆地改成水也就是grid[i][j] 0。这种做法叫“原地标记”能省下不少内存。但原题如果要求不能修改输入矩阵你就必须老老实实建一个visited矩阵。网格DFS最容易犯的错是边界判断漏写。i 0 or i m or j 0 or j n这四个条件缺一不可少一个都可能产生数组越界甚至把矩阵外围当成合法节点。另一个容易犯的错是方向数量斜对角到底允不允许走题目没说的话默认只走上下左右四个方向不要随意扩展成八方向。从网格DFS还能延伸出走迷宫最短步数的问题不过一旦要求最短步数DFS就不合适了得切换到BFS。网格DFS适合的是连通域统计、寻找所有可行路线不管长短、数独式填法判定等场景。5. 回溯法DFS在状态空间里的真正发力点5.1 从全排列看回溯模板树的DFS遍历的是一颗已经存在的树但很多问题里我们面对的“搜索空间”并不是一颗实体树而是一颗靠递归一层层“生成”出来的状态树。每一次做出选择就进入下一层这一层的所有可能选择就是当前节点的孩子节点。比如全排列问题第一个位置可以放数组中任意一个数第二个位置可以放剩下任意一个数……直到所有位置都被填满。这棵树是隐式的需要DFS去展开它。def permute(nums): n len(nums) res [] path [] used [False] * n def backtrack(): if len(path) n: res.append(path[:]) return for i in range(n): if used[i]: continue # 做选择 used[i] True path.append(nums[i]) backtrack() # 撤销选择 path.pop() used[i] False backtrack() return res这套“做选择—递归—撤销选择”的结构是回溯法的标准姿势。为什么必须撤销选择因为path和used在当前递归层是共享的如果不把状态恢复成进入这一层之前的样子上一层选择其他数时残留的状态会让结果错得离谱。path[:]复制新列表再放进结果也是无数人踩过的坑直接res.append(path)的话后续path.pop()会把已经存进结果里的排列改得面目全非。5.2 组合、子集、N皇后同一模板的衍生一旦掌握了全排列模板组合、子集、N皇后都只是排列的变体。求子集时每个数选或不选都是分支所以不需要used数组只要记录当前的起始下标避免回头重复选取。代码框架里把“每个位置看成一个状态”变成“每个数看成一个决策点”就行。N皇后问题更典型每一行必须放一个皇后每一行有n列可选但列和斜线会冲突。所以用三个数组记录列、主对角线、副对角线的占用情况然后一行一行地做选择。问题类型状态定义剪枝依据全排列已经选择的数字集合每个数字只能用一次组合当前选到哪个数只能往后选避免重复组合子集当前元素取或不取不重复取同一元素N皇后前i行皇后的摆放位置行列、主副对角线不冲突这些回溯问题本质上共享同一个递归骨架区别只在于“每个状态可选的范围”和“冲突检测规则”。所以千万别去背一个个题号把模板内化成自己的东西遇到新题只需要改两处一是构造状态的方式二是剪枝条件。6. 剪枝优化让DFS从指数爆炸变得可用6.1 剪枝的本质与三类常用剪枝DFS最大的痛点是复杂度指数级。全排列n!子集2^n这种增长速度意味着n一旦到20以上裸递归基本跑不出结果。剪枝就是在递归搜索树的某些分支还没走到头时提前判断“这条路不可能产生有效解”直接放弃减少无效计算。剪枝的核心要求是只剪掉不可能的分支绝不能把正确答案剪掉。我按自己的经验把剪枝分成三类。第一类是可行性剪枝当前状态明显不满足约束条件直接返回。N皇后里检测到斜线冲突就立即放弃这一层数独里当前填写数字与同行同列同宫冲突就跳过。第二类是最优性剪枝常见于需要找最优解的DFS场景已经算出当前最优解是10步现在这条路径已经走了超过10步那就没必要继续。这种剪枝也叫“分支限界”。第三类是重复状态剪枝通过visited或哈希集合记住已经搜索过的状态下次遇到相同状态直接跳过避免重复计算。一个很直观的例子是数独。标准数独的暴力DFS会尝试81个格子里的所有填充组合如果不剪枝理论上要算到宇宙毁灭。实战做法是每填一个格子就检查当前数字是否和所在行、列、宫冲突一冲突立刻回头再结合“选择剩余可填数字最少的空格优先填”这种启发式策略普通数独几乎瞬间出解。6.2 复杂度评估与应对大规模数据面试和实际项目里判断DFS是否可行我一般直接卡输入规模。n不超过10全排列勉强可以跑n到15必须加剪枝而且最好用带启发式的顺序优化n到20要考虑子集类问题是否已经超时n超过30基本就别想裸DFS了。数据规模典型复杂度是否适合裸DFSn 1010! 3628800勉强可以n 202^20 1048576适合但要小心常数n 302^30 ≈ 10亿必须配合强剪枝n 100指数级放弃DFS换DP或图算法判断一个搜索题能不能用DFS可以按这个思路走先估算最大搜索深度再看每一层的宽度估算整棵搜索树的节点规模。节点规模在百万级且剪枝明显有效放心用DFS节点规模大到天文数字又找不到强剪枝条件赶紧换思路。DFS不是万能的但“能剪枝的DFS”往往比很多花哨算法更实用因为它的实现逻辑足够简单不容易出隐藏错误。7. 实战中的甩坑记录与排错思路7.1 忘记回溯导致的状态污染我记得有次调试一个子集问题的递归输出结果里出现了大量重复集合。一开始怀疑是去重逻辑没写好后来打印每一步的path和start发现问题出在递归返回后没有把path里的最后一个元素弹出。因为path是共享可变对象上一层递归还会复用这个列表残留的元素会让后续组合信息错乱。那次之后我养成一个习惯写回溯递归时先确认三件事。第一递归入口之前有没有保存当前状态第二递归返回之后有没有完整恢复现场第三把结果存进全局容器时有没有做深拷贝。这三个问题只要有一个出错结果大概率是错的而且错误非常隐蔽小数据集看不太出来数据量一大就全乱套。7.2 递归深度限制与显式栈的取舍还有个坑是Python的递归深度。有一次我在某跨平台系统里要遍历依赖关系图图的深度比预想大得多递归到大约900多层时直接抛RecursionError。当时第一反应是调sys.setrecursionlimit(10000)但后来发现治标不治本深度上万层时即使不报错递归性能也明显下降而且Python的函数调用开销本身就比循环大。更稳的做法是改成显式栈。显式栈的好处有三个不受递归深度限制每一步的压栈和弹栈都看得见方便调试能精确控制遍历顺序不会因为系统栈的隐式行为产生意外。代价就是代码会啰嗦一些。如果只是做题、演示算法递归版本完全够用如果写进生产环境处理大型图结构我会优先考虑显式栈实现。7.3 如何验证DFS自己的写法是对的最后分享一个排错方法论。写完DFS代码不要直接蒙头跑大数据先用一个极小的输入手推一遍比如只有4个节点的链状图或者3个数字的全排列。把递归的每一层进出情况画在纸上和自己代码的打印日志对照。如果前几个状态就能对得上后面出错的可能性就低很多。我在调试时会专门打印三个信息进入递归时的当前节点、离开递归时的当前节点、当前路径快照。这样能清楚看到每个分支的完整生命周期。等到代码跑通再把这些日志删掉换成正式的数据验证。这个方法看起来笨但应对DFS这种“看不见摸不着”的递归状态比任何高级调试器都直观。如果你也在啃搜索之DFS这一块我建议你按这个顺序练先手写二叉树三种遍历的递归版再改手动栈然后做一个图连通性DFS再做一道回溯全排列最后加一道带剪枝的搜索题。跑通这一个系列你对DFS的理解会从“背模板”变成“真正的直觉”。我相信在后续接触动态规划、状态压缩、树形DP的时候你会感谢当初把DFS的底层机理啃明白了。