很多刚接触算法的朋友总会把 DFS 和 BFS 当成两个“必须背下来的模板”却很少去想它们到底在解决什么问题。其实这两个算法本质上是同一种思想的两条路搜索。从一个状态出发沿着可能的路径去探索目标状态DFS 是“一条路走到底走不通再回头”BFS 是“一层一层往外扩像水波一样扩散”。不管你是准备面试、刷题、打竞赛还是做路径规划、游戏 AI、编译器里的 AST 遍历几乎都绕不开这两个算法。这篇文章我会从原理、实现、对比到剪枝优化把 DFS 和 BFS 拆开讲透附带一些我踩过的坑尽量让新手能直接上手也让有一定基础的人能查漏补缺。1. 先搞懂搜索算法在解决什么问题1.1 搜索的本质是“状态空间的遍历”很多人把 DFS/BFS 单纯理解为“图的遍历算法”这个说法不算错但格局小了。搜索算法真正处理的对象是状态空间——所有可能的状态以及状态之间的转移关系。一个状态可以是一张棋盘、一个排列、一个坐标点甚至是一组变量的取值一条转移路径就是一次操作、一步移动、一次赋值。举个例子走迷宫就是一个典型的状态空间当前所在坐标是状态上下左右移动一步就是状态转移。你要找从入口到出口的路线本质上是在状态空间里搜索目标状态。再比如全排列问题从空序列开始每次往末尾追加一个未使用的数字直到长度达到 n这同样是在一个由部分排列组成的空间里搜索。DFS 和 BFS 并不关心状态具体是什么它们只是两种遍历这个空间的策略。你给它们一个起点、一组邻接关系、一个目标判定条件它们就能老老实实地把能走到的地方全部走一遍。理解了这一点你就不会再觉得 DFS/BFS 只是数据结构课的“图的遍历”那么简单了。1.2 为什么说 DFS 和 BFS 是“暴力枚举”的骨架算法领域有个词叫暴力枚举意思是把所有可能的情况都试一遍。朴素暴力是一层一层嵌套 for 循环可当循环层数不确定时for 循环就没法写了。这时候 DFS 就登场了——它用递归/栈的方式把“不确定层数的循环”变成了“每次调用处理一层”这让枚举任意深度的组合成为可能。BFS 承担的任务则更偏“层次推进”。它不追求一次钻到底部而是把当前能到达的所有状态都先摸一遍再考虑下一步。这看起来比 DFS 更“笨”但在求解无权图最短路径、最少步数、层次类问题时BFS 有天然优势第一次碰到目标状态的路径一定是步数最少的。所以别把 DFS/BFS 当成两个孤立的模板它们是你把“暴力枚举”落地为代码的两种基本手段。后续所有的优化比如剪枝、记忆化搜索、双向 BFS、A* 算法都是在这两套骨架上做文章。2. DFS深度优先搜索的原理与实现2.1 核心思想一条路走到黑撞了南墙再回头DFS 的策略非常简单粗暴从起点出发沿着某个分支一直往下走直到不能再走再回退到最近的分叉点换一条分支继续。这个“回退”动作叫回溯是整个 DFS 的灵魂。我个人的理解是把 DFS 想象成“在纸上画一棵树用笔尖从根一直描到某个叶子画不下去就倒回上一节点再换个方向描”。这种深度优先的访问顺序决定了它天然的适合递归实现因为函数调用栈本身就带着“当前路径记忆”的能力。看一个最简单的例子用 DFS 遍历一棵二叉树。逻辑只有三步先访问当前节点然后递归访问左子树再递归访问右子树。换成图也一样区别只是图要记录哪些节点访问过避免在环里死循环。2.2 递归实现与显式栈实现两种写法的取舍递归实现是 DFS 最直观的写法因为递归调用的过程本身就是“深入——返回——再深入”。比如输出从 0 到 n-1 的全排列def dfs(nums, path, used, res): if len(path) len(nums): res.append(path[:]) return for i, num in enumerate(nums): if used[i]: continue used[i] True path.append(num) dfs(nums, path, used, res) used[i] False path.pop()这里used[i] True表示“占用这个数字”path.append表示“走到下一个状态”等递归返回后used[i] False和path.pop()负责撤销选择恢复现场。这一步掉的人很多忘了恢复现场结果就是后面的分支全乱套。递归写法的优点是代码简洁、思路清晰缺点是递归深度受系统调用栈限制。实践里 Python 默认递归深度大约是 1000 层8 皇后没问题但要处理 10 万层深的图直接当场 RecursionError。这时候就要用显式栈模拟 DFS把“下次该访问谁”放在自己管理的栈里循环弹出、压入。写法比递归繁琐但深度不再受调用栈限制而且函数调用开销更小。def dfs_stack(graph, start, visited): stack [start] while stack: node stack.pop() if visited[node]: continue visited[node] True # 处理当前节点 for neighbor in graph[node]: if not visited[neighbor]: stack.append(neighbor)注意这里有个我想强调的细节显式栈 DFS 的访问顺序不一定和递归版本完全一致因为入栈顺序和出栈顺序会反转。如果你依赖遍历顺序比如拓扑排序、路径记录要么控制入栈顺序要么在入栈时就打标记而不是出栈时打标记否则可能重复入栈。2.3 回溯时为什么要“恢复现场”恢复现场是 DFS 最容易翻车的地方也是最值得单独说的一点。在全排列 / 组合 / 棋盘搜索这类问题里你每尝试一条路都会改变当前状态比如使用过的数字列表、棋盘上已经摆放的皇后位置。如果尝试完不撤销就会污染后续同一层的其他分支。我习惯在写任何 DFS 前先问自己三个问题当前路径上的状态变量是什么进入递归前要做什么修改递归返回后要撤销哪些修改如果把这三件事想清楚恢复现场基本不会漏。还有个小技巧能用“拷贝一份新状态传进去”代替“修改再撤销”就不要依赖恢复现场。比如 Python 里传path [num]而不是path.append(num)再pop()代码更安全代价是每次递归都会复制一份列表空间和耗时更高。小数据量无所谓大数据量还是老老实实修改再撤销。3. BFS广度优先搜索的原理与实现3.1 核心思想一圈一圈往外推像水面波纹BFS 和 DFS 正好相反它是从起点出发先把所有能一步到达的状态全部访问完再从这些状态出发访问两步能到达的状态以此类推。如果用一张图来形容就是从起点为中心一圈一圈扩散的波纹每一圈代表“距离起点相同步数”的所有节点。这种访问顺序决定了 BFS 有个 DFS 没有的香饽饽性质在无权图中首次搜索到目标节点时的路径长度一定是最短的。因为 BFS 是按层推进的第一圈是距离 1 的所有节点第二圈是距离 2 的所有节点……目标节点第一次出现时必然位于当前这一圈也就是最小层数。这个性质让 BFS 成了求解“最少步数 / 最短路径 / 最少操作次数”类问题的首选。比如走迷宫求起点到终点的最短步数、字符串经过多少次替换能变成目标串、八数码最少移动几次都可以直接套 BFS。3.2 队列实现与层级控制两种常见写法BFS 的标配是队列。每次从队头取出一个状态把它所有没有访问过的邻居放入队尾直到队列为空。如果用迷宫求最短步数需要知道节点所在的层级通常有两种写法。第一种是“每个状态带步数”from collections import deque def bfs_shortest_path(maze, start, target): rows, cols len(maze), len(maze[0]) visited [[False] * cols for _ in range(rows)] q deque() q.append((start[0], start[1], 0)) # 坐标和步数 visited[start[0]][start[1]] True while q: x, y, step q.popleft() if (x, y) target: return step for dx, dy in ((1,0),(-1,0),(0,1),(0,-1)): nx, ny x dx, y dy if 0 nx rows and 0 ny cols and not visited[nx][ny] and maze[nx][ny] ! 1: visited[nx][ny] True q.append((nx, ny, step 1)) return -1第二种是“按层逐圈处理”更利于统计每一层的节点数或做更复杂的层级逻辑from collections import deque def bfs_by_level(graph, start): visited set([start]) q deque([start]) while q: level_size len(q) # 当前层的节点数 for _ in range(level_size): node q.popleft() # 处理 node for nxt in graph[node]: if nxt not in visited: visited.add(nxt) q.append(nxt) # 到这里说明一层已经处理完第二种写法在做二叉树的层序遍历、求每一层最大值、统计扩散轮数时特别顺手。刚开始学 BFS 的朋友我建议两种写法都练熟。3.3 BFS 的空间代价为什么说它“空间换时间”BFS 的代价也很明显——空间消耗通常比 DFS 高。DFS 只用维护一条路径栈的深度一般不会超过状态空间的深度BFS 的队列要同时保存一整层的节点下一层又会在这一层全部出队前陆续入队所以最坏情况下队列规模可以接近节点总数空间复杂度是 O(V)。比如一张网格图 1000×1000BFS 的队列和 visited 数组可能要存几十万个坐标而 DFS 的递归栈深度最多几百上千层反而更省内存。面试里有人问我 DFS 和 BFS 怎么选我一般先看问题要最短路径就 BFS要枚举所有可能路径就 DFS然后再考虑空间是否紧张。另外提一句BFS 的 visited 标记要在入队时就设置而不是出队时设置。因为如果出队时才标记同一个节点可能被多个邻居重复入队队列里出现大量重复状态轻则浪费内存重则直接超时。这个细节我用“入队即锁”四个字记在心里。4. DFS 和 BFS 到底怎么选核心对比与场景分析4.1 一张表看懂两者差异很多入门指南会把 DFS/BFS 写成两个仿佛对立的方法其实它们面对同一个状态空间只是访问顺序不同。我把它们的关键差异列出来方便对照对比维度DFS深度优先BFS广度优先遍历顺序沿着分支尽可能深按层从左到右 / 从近到远核心数据结构栈递归时由系统调用栈承担队列空间复杂度O(深度)一般情况下较小O(节点数)最坏可能很大是否适合求最短路径否首次找到不保证最短是无权图中首次找到即最短是否适合枚举全部解是回溯可以遍历所有分支可以但通常不如 DFS 直观是否适合检测连通性是是实现难度递归简单显式栈略繁琐队列逻辑固定模板性强典型应用全排列、组合、N 皇后、路径枚举、拓扑排序、连通块最少步数、二叉树的层序遍历、最短路径、单词接龙这张表不是让你死记硬背而是让你在拿到问题后先用几秒钟做判断如果需求是“找到任意一条可行路径”DFS 往往更省事如果需求是“找到最短的那条路径”先考虑 BFS。4.2 按问题类型选算法的实战判断逻辑我做题和写工程代码时一般按下面这个思路来判断用 DFS 还是 BFS。第一类问题求方案数量 / 枚举所有方案。比如给一组数输出所有不重复的子集或者在 8×8 棋盘上放 8 个皇后求所有摆放方案。这类问题必须遍历所有可能分支DFS 天然适合再配合回溯和剪枝。第二类问题求最短步数 / 最短路径。比如从一个单词变成另一个单词每次只能改一个字母或者在迷宫里从左上角走到右下角问最少走几步。答案只要一个最值BFS 第一次搜到答案时就已经是最优解直接返回即可。第三类问题连通性判断或连通块计数。比如统计一张图里有多少个互不连通的岛屿。这类题 DFS 和 BFS 都行DFS 的代码更短但要注意递归深度BFS 更稳但队列开销大。我一般随心情选如果题目数据范围很大优先 BFS 或者显式栈 DFS。第四类问题拓扑排序。这个特殊一点经典解法是 BFSKahn 算法配合入度表。DFS 也能做拓扑排序但要额外标记节点的访问状态和完成时间容易写错实战里我首推 BFS。4.3 面试中怎么快速给面试官讲清选型理由算法工程师面试里面试官很少直接问“DFS 和 BFS 是什么”更多是抛一道题让你现场做比如“给你一个矩阵1 代表陆地 0 代表水统计岛屿数量”。这种时候你不仅要写出代码还要能说明白为什么选这个算法。我常用的回答框架是先把问题抽象成“状态 x 坐标 状态转移 x 上下左右移动”然后指出这是在图或网格上的搜索问题。如果目标是求最短步数就说 BFS 按层扩展天然保证首次访问到目标时步数最短如果目标是找所有可能路径就说 DFS 配合回溯可以穷尽所有分支再用剪枝控制规模。这种“先说抽象再说选型最后说复杂度”的顺序很容易让面试官觉得你思路清楚。5. 让暴力枚举活下来剪枝与优化的实战经验5.1 为什么原生的 DFS/BFS 经常超时很多新手把 DFS 模板背熟了却发现一到大数据量的题目就超时。原因很简单搜索算法的本质是遍历状态空间而状态空间往往是爆炸式增长的。举例来说n 个元素的全排列有 n! 个状态一个普通国际象棋棋局的状态数更是天文数字。即使 BFS 在最坏情况下也要遍历所有节点所以不加任何优化的搜索本质就是暴力枚举只适合状态空间很小的问题。我自己入行那会儿吃过不少亏总以为“搜索算法万能”结果一个 20 个数字的子集和问题把整个程序卡死。后来才知道搜索的真正功夫在于剪枝——在递归还没走到叶子时就提前判断这条路不可能出解直接放弃。5.2 三类最常用的剪枝策略第一类是可行性剪枝。在递归过程中如果当前状态已经不可能满足约束条件立刻返回。比如 N 皇后问题里当前行摆放的皇后和之前任意皇后同列或同对角线说明这个位置不合法直接跳过不用再往下递归。第二类是最优性剪枝。这类剪枝适用于求最优解的问题。如果在搜索中已经找到了一个答案代价是 ans那么后续任何一条路径的代价只要超过或等于 ans就不用再继续搜索了。比如走迷宫找一条代价最小的路走到半路发现步数已经超过当前已知最优解就可以马上回头。这类剪枝需要维护一个“当前最优解”的全局变量并且要保证路径代价是单调递增的否则剪枝可能剪掉还没出现的更优解。第三类是调整搜索顺序。这个很多人会忽略。同一个 DFS分支的尝试顺序不同搜索耗时可能差出几个数量级。比如求解“从一堆数字里挑出若干个数使总和最接近目标”这类问题先把数字从大到小排序再做搜索往往能更快逼近答案配合最优性剪枝后效果立竿见影。因为大的数字能快速让部分和接近目标提前触发剪枝条件。5.3 用“数独求解”演示剪枝如何落地数独是个很好的剪枝教学案例。朴素的 DFS 就是从第一个空格开始依次尝试填入 1~9然后递归填下一个空格直到填完或冲突。如果不剪枝9^81 的状态空间想都不用想。常见做法是“预剪枝”每次只从可选数字最少的空格开始填。因为空格可选数字越少分支越少DFS 的搜索树就越窄。再加上维护每一行、每一列、每一宫的数字占用标记每次尝试数字前先查标记冲突就跳过。我自己实现的数独求解器核心就是两个优化一是构建候选集把每个空格可填的数字预先算出来二是每次递归时选候选集长度最小的空格展开。就这么两行决策逻辑已经能应付大部分 9×9 数独。这说明剪枝很多时候不需要花哨技巧选对展开顺序就是最大的优化。5.4 记忆化搜索从 DFS 到动态规划的桥搜索优化里还有一个和 DFS 强相关的手段叫记忆化搜索。如果 DFS 递归过程中会反复计算相同状态就可以用一个数组或哈希表把该状态的结果存下来下次遇到直接取用。最经典的例子是斐波那契数列直接递归会重复计算 fib(2) 无数次复杂度 O(2^n)加一个 memo 数组后复杂度降到 O(n)。更进一步很多动态规划问题都可以改写成记忆化搜索的形式且不用想状态转移顺序代码反而更好写。我的建议是如果你觉得某个 DP 题的状态定义想不清楚先尝试用 DFS 记忆化去写把状态参数直接写在递归函数里让递归帮你理顺依赖关系。等你写顺了再回头看它的递推公式往往就豁然开朗。6. 常见问题与排查技巧实录6.1 死循环图里有环却忘了标记访问状态DFS 和 BFS 在图结构上最容易出的问题就是死循环。原因很简单图不一定是棵树它可能有环如果你只往下走不回头最终会转回已经访问过的节点然后无限递归。解决方式就是加 visited 标记。这里我有两个经验教训第一visited 的范围必须覆盖所有能到达的节点比如网格题里 visited 数组要和网格大小一致第二visited 的标记时机要正确。BFS 是入队时标记DFS 是“在进入递归前标记”或“递归函数开头标记”总之不能等到“准备访问邻居”时才标记上一层否则同一层可能被重复扩展。6.2 递归爆栈深度太大怎么办用递归写 DFS最怕数据范围给得狠。一个 10 万层的链状图Python 默认递归深度不到 1000直接报 RecursionError。解决办法有三个一是调大递归深度限制Python 里可以用sys.setrecursionlimit(10**6)但这个方法治标不治本内存不一定够而且某些环境/语言不支持二是改成显式栈写法完全避开系统调用栈三是换 BFS如果题目不要求深度优先特性BFS 往往更稳。我在实际刷题中碰到 1 万层以上的递归一般会直接放弃递归写法切换显式栈。别跟系统栈过不去它真的会崩。6.3 BFS 队列爆内存状态重复入队了BFS 超内存的例子我遇过不少尤其是地图很大的题。最隐蔽原因是 visited 标记设晚了导致同一个点被放入队列很多次。比如从四个方向都能到达某个点如果这个点还没入队时就已经被别的邻居“看到”但你不做标记它就会被重复 push。排查方法很简单在入队逻辑里打印节点 id 或坐标看看队列长度是不是先暴涨再回落如果同一时间队列里出现大量重复状态十有八九是标记时机不对。修复方式就是在q.append之后立即把该状态标记为已访问。6.4 用 DFS 求最短路径结果不对这也是高频问题。DFS 能求出从起点到终点的路径但它找到的第一条路径完全取决于分支访问顺序不一定是步数最短的。如果你用 DFS 求“最少步数”除非你把所有路径都遍历一遍取最小值否则结果很可能是错的。我见过有人写 DFS 维护一个全局最小值变量来求迷宫最短路径也能跑通但复杂度是指数级。对于无权图的最短路径正确选择是 BFS如果权重不同那就要升级到 Dijkstra 或 A* 这类算法DFS 的思路就基本不适用了。6.5 剪枝剪过头正确答案被丢掉了剪枝的本质是“把不可能产生可行解/最优解的分支砍掉”但判断“不可能”的标准一旦过严就会把还可能出解的分支也砍掉导致答案不完整或根本不是最优解。这个坑的典型例子是最优性剪枝里维护的当前最优解没有正确初始化或者剪枝条件把“相等”的情况也剪掉了。比如要求“路径代价不超过 ans 才继续”如果你把条件写成 ans就返回而 ans 又恰好等于目标解那所有等于 ans 的路径都会被丢掉。建议剪枝条件宁松勿紧先保证答案正确再逐步收紧剪枝范围来提速。6.6 常见问题速查表现象可能原因解决思路程序卡死 / 无限递归图中有环且未标记 visited入口即标记递归前判断 visited递归深度过大报错系统调用栈不够调大递归上限或改写显式栈或换 BFS队列内存暴涨visited 标记过晚入队时立刻标记DFS 求最短路径结果错误DFS 不保证首次路径最短换 BFS无权图用队列按层扩展输出结果缺方案剪枝条件过严放宽剪枝先保证正确再优化恢复现场漏写路径变量被后续分支污染梳理“进入递归前改了什么返回后还原什么”结果和预期只差一点遍历分支顺序影响答案检查搜索顺序看是否需要排序或调整方向数组顺序7. 最后再分享一点我的个人习惯说了这么多原理和代码最后聊点我实际工作的体会。我写搜索题有一个固定流程先把问题抽象成“状态 转移”明确目标和约束然后判断目标是“最短/最少”还是“所有方案”接着选择 BFS 或 DFS 并写最初的暴力版本最后再看数据范围决定要不要加剪枝或记忆化。这个流程帮我避免了很多“一上来就优化”的坏习惯。我见过不少同学拿到题直接写剪枝结果剪枝条件写得漏洞百出反而连暴力解都写不对。我的建议是先用朴素 DFS/BFS 把逻辑跑通哪怕会超时至少答案正确这能帮你确认算法选型没问题然后再逐步加优化一步一步验证每一步的耗时变化。另一个小技巧是遇到状态复杂的题先把状态压缩成整数或字符串再用字典做记忆化。比如一个 3×3 棋盘的状态可以转成一个九位数BFS 里用set存储已访问状态既省内存又查得快。这种“状态编码”的能力在刷题和做路径规划项目里非常实用值得专门练一练。DFS 和 BFS 只是搜索世界的起点。把它们吃透之后你会发现记忆化搜索、动态规划、双向 BFS、A* 算法、Dijkstra 这些更高级的工具都建立在同样的状态空间遍历思想上。先把这两个基础算法写熟、写对后面学什么都快。