1. 从“找东西”说起DFS和BFS到底在解决什么问题如果你接触算法有一阵子了肯定绕不开两个经典搜索策略深度优先搜索DFSDepth First Search和广度优先搜索BFSBreadth First Search。它们几乎是所有图论算法、路径规划、状态空间搜索问题的基础也是面试里最高频的“手撕代码”题目。用大白话说DFS和BFS解决的核心问题是在一个“地图”上怎么系统地逛完所有地方或者怎么找到某个目标位置。这个“地图”可以是真实的城市道路也可以是抽象的数据结构比如二叉树、状态转移图、迷宫格子甚至是你手机App里的社交关系网络。DFS的特点是“一条路走到黑撞了南墙再回头”BFS则是“一圈一圈往外扩像水波一样推开”。我自己在刷题和实际项目里几乎每周都会用到这两个算法。列出目录、文件清理、网络拓扑探测、连连看消除、迷宫寻路……到处都有它们的身影。这篇文章不打算讲那种纯书面的“定义伪代码”而是用我实际的踩坑经历、手写代码和调试过程把DFS和BFS彻底讲透。这篇文章适合什么人看如果你刚开始学数据结构被递归绕晕过如果你刷LeetCode一到图相关题目就卡壳或者你工作中需要处理树形结构、寻路逻辑这篇都可以帮你把基础打牢。我会尽量用最直白的语言把原理、代码、场景、复杂度一次说明白。2. DFS和BFS的核心思路对比一个是“钻”一个是“摊”2.1 DFS不撞南墙不回头的“探险家”深度优先搜索的核心策略可以理解成一个在迷宫里探险的人每到一个岔路口就挑一个方向走一直往前走直到走不通了没有路或者访问过了就退回上一个岔路口再换另一个方向继续走。这种策略叫LIFO后进先出天然和“栈”或者“递归调用栈”绑定。二叉树场景下DFS就是先一路向下从最左子节点开始处理图场景下DFS就是沿着一条邻接边不断深入直到遇到死胡同。它不关心“起点附近”还有没有路径它只关心“当前路径的尽头在哪”。我在实际写DFS的时候脑子里会画一个“栈的入栈出栈”过程。比如一个简单的二叉树1 / \ 2 3 / \ 4 5DFS从节点1出发如果先走左边1 - 2 - 4。4没有子节点了退回到2再走2的右边到55也到底了退回到1再走右边到3。所以遍历顺序是 1, 2, 4, 5, 3。这个过程本质上就是一个“栈”每进入一个节点就压栈每回溯一个节点就弹栈。递归方式可以说是DF的“语法糖”因为递归本身调用栈就帮你完成了压栈和弹栈。2.2 BFS层层推进的“排头兵”广度优先搜索的核心策略则是“按层推进”。从起点出发先把所有和起点相邻的节点都访问一遍然后访问“相邻节点的相邻节点”以此类推。这种策略叫FIFO先进先出天然用队列实现。同样是上面那棵二叉树BFS的顺序就是1 - 2 - 3 - 4 - 5。你会看到它是先把同一层的节点全部访问完才进入下一层。这个特性在“最短路径”类问题里极其重要因为第一次用BFS从起点抵达某个目标节点时走的路径一定是最短的在无权图中。生活化类比DFS是“你拿着手电筒走进一个山洞走到尽头再回头探索另一条分支”BFS是“你往平静的水面丢一颗石子波纹一圈一圈向外扩散”。这两种翻译方式决定了它们适合的场景完全不同。2.3 一张表把关键区别说清楚对比维度DFSBFS核心数据结构栈递归调用栈或显式栈队列访问顺序深度优先纵向深入广度优先横向展开空间复杂度树/图最坏O(h)h为深度最坏O(w)w为最大宽度是否适合找最短路径不一定找到路径可能绕远适合第一层抵达即为最短是否容易递归实现非常自然不自然适合迭代队列典型应用拓扑排序、连通分量、回溯、剪枝最短路径、社交网络层级遍历、二分图检测一个特别容易让人迷糊的地方DFS在“找路径”时不一定找到最短的BFS在“找是否存在路径”时并不比DFS省时间。这取决于你具体想解决什么问题。后面我会用具体例子展开。3. 手写DFS递归版和栈版“双管齐下”3.1 从二叉树开始DFS递归模板写算法题和工程代码我建议先从最简单的模板练起。二叉树是最适合练DFS的结构因为它天然有“左”、“右”两个方向。下面这段是二叉树前序遍历的DFS递归实现# 二叉树节点定义 class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right def dfs_preorder(root): result [] if root is None: return result def traverse(node): if node is None: return result.append(node.val) # 前序先访问当前节点 traverse(node.left) # 深入左子树 traverse(node.right) # 深入右子树 traverse(root) return result这里的关键点是终止条件node is None和递归调用顺序先左后右。我第一次学的时候总喜欢纠结“为什么要有终止条件”后来明白递归必须有一个“出口”否则就会无限循环程序直接爆掉。3.2 改成显式栈递归的“平行替代”递归虽好但有两个硬伤一是深度太深可能栈溢出Python里默认递归深度大约在1000二是有时候你需要完全控制遍历过程。这时候可以用显式栈模拟递归def dfs_iterative(root): if root is None: return [] result [] stack [root] while stack: node stack.pop() result.append(node.val) # 注意顺序栈是后进先出所以先压右子树再压左子树 if node.right: stack.append(node.right) if node.left: stack.append(node.left) return result很多人第一次写都会踩这个坑如果先append左子树再append右子树出栈顺序就变成先右后左了。解法很简单先把右子树压栈再把左子树压栈这样左子树会先出栈保持了“先左后右”的访问顺序。3.3 网格DFS常用模板回溯剪枝在LeetCode和实际项目中更常见的是“网格图上的DFS”比如岛屿数量、迷宫寻路、单词搜索。这种题目的特点是每次可以往上下左右四个方向走。我习惯写这样一个模板def dfs_grid(grid, r, c, visited): rows, cols len(grid), len(grid[0]) # 越界或已访问或不可通行 if r 0 or r rows or c 0 or c cols: return if visited[r][c]: return if grid[r][c] 0: # 假设0是墙 return visited[r][c] True # 继续向四个方向递归 dfs_grid(grid, r - 1, c, visited) # 上 dfs_grid(grid, r 1, c, visited) # 下 dfs_grid(grid, r, c - 1, visited) # 左 dfs_grid(grid, r, c 1, visited) # 右这个模板我几乎不变地在用核心思路就是“三剪”越界剪、重复剪、障碍剪。写递归的时候一定要记住先判断要不要返回再标记访问状态最后做递归。特别是标记访问状态很多人漏了这一步结果同一个格子被反复遍历直接死循环。3.4 我踩过的递归坑忘了“回溯”DFS里还有一个特别容易出问题的概念回溯。如果你做的是“枚举所有路径”这种题递归返回后需要“撤销状态”。举个例子从起点出发找所有路径我在每个格子记录“当前路径上”递归完准备回到上一层时必须把这个标记清掉否则上层会以为这个格子还在当前路径里导致路径拼错。def dfs_with_backtrack(grid, r, c, path, visited): if (越界或障碍): return path.append((r, c)) visited[r][c] True if (r, c) target: print(path) # 找到一条路径 # 尝试四个方向 for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]: dfs_with_backtrack(grid, r dr, c dc, path, visited) # 回溯恢复状态 visited[r][c] False path.pop()这里的“撤销”就是回溯的灵魂。我一开始用回溯做子集、排列时屡屡报错后来发现都栽在“忘掉回溯”这一步上。把这句visited[r][c] False记在心里比背任何模板都有用。4. 手写BFS队列模板与最短路径4.1 二叉树的BFS按层遍历BFS在二叉树里就是层序遍历这也是我在项目里用得最多的遍历方式。比如渲染树形目录、计算树的宽度都靠它。代码如下from collections import deque def bfs_level_order(root): if root is None: return [] result [] queue deque([root]) while queue: level [] level_size len(queue) # 关键记录当前层的节点数 for _ in range(level_size): node queue.popleft() level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(level) # 按层放入结果 return result这里有一个小技巧新手经常忽略每次循环时一定要先记录len(queue)。因为你在for循环里会往队列中append新的节点队列长度一直在变如果不提前存下来就无法准确切分“这一层”和“下一层”。我实战中见过不少同事在这上面翻车。4.2 网格BFS从起点向四周扩散BFS在网格图里最经典的应用就是求最短路径。比如有一个01矩阵1代表可走0代表墙问从左上角到右下角最少要走几步from collections import deque def shortest_path(grid): if not grid or not grid[0]: return -1 rows, cols len(grid), len(grid[0]) # 方向数组按上下左右 directions [(-1,0), (1,0), (0,-1), (0,1)] # visited数组兼作步数记录 visited [[False]*cols for _ in range(rows)] queue deque() queue.append((0, 0, 0)) # 第三个元素表示步数 visited[0][0] True while queue: r, c, dist queue.popleft() # 到达终点 if (r, c) (rows - 1, cols - 1): return dist for dr, dc in directions: nr, nc r dr, c dc if 0 nr rows and 0 nc cols: if not visited[nr][nc] and grid[nr][nc] 1: visited[nr][nc] True queue.append((nr, nc, dist 1)) return -1 # 没有可达路径我通常在BFS里用一个visited数组同时充当“去重表”和“已访问标记”。第一次访问某个格子时的步数就是最短步数因为BFS的层序性质保证了这一点。有些贪心做法会想省掉visited直接用距离数组判断但visited表更直观也更好调试。4.3 双向BFS一个优化技巧如果起点和终点都确定而且图规模很大可以用双向BFS。思想是从起点和终点同时开始BFS每次扩展节点数少的一侧直到两侧相遇。双向BFS能把搜索空间从“一个巨大的洋葱”切成“两个较小的洋葱”实际节省大量时间和内存。我在处理一些大迷宫问题时经常使用效果非常明显。但要注意双向BFS代码复杂度更高容易出错需要一个dist_from_start和一个dist_from_end两个哈希表来存储状态。如果只是小规模练习题写普通BFS就够了。5. DFS和BFS的复杂度分析千万不要只会背结论5.1 时间复杂度和空间复杂度很多人在面试里答“DFS时间复杂度是O(VE)”时其实并不清楚为什么。这里解释一下V是顶点数节点数E是边数连接关系数量。无论DFS还是BFS你都会把每个节点访问一次同时把每条边检查一次。所以遍历整张图的时间复杂度是O(VE)。如果是二叉树E V - 1所以通常是O(V)也就是 O(n)n为节点数。空间复杂度DFS最坏情况是递归深度/栈深度也就是树的高度表示为 O(h)在图里极端情况下可能是 O(V)。BFS最坏情况是队列同时容纳某一层所有节点若图是“网”可能达到 O(V)。我并不建议大家死记这个结论而是学会推导。我面试别人的时候最希望他能画一个小图然后说明“每个点进一次每条边出一次”这就是真正的理解。5.2 为什么BFS第一次到达目标就是最短路径这是BFS的“王炸”属性。原因是BFS在所有路径上“同时推进”每推进一步所有当前已知节点离起点的步数最多为k。当目标第一次出现在队列中时它的步数必然是所有从起点到该点路径中最小的因为如果还存在更短路径那条路径上的节点应该更早被访问到从而更早把目标纳入队列。我用一个生活例子来记忆你同时向十几个快递站打电话问某个包裹在哪每个电话都要等对方查几秒钟。BFS就相当于所有电话同时打出去、同时得到回复因此谁先回“到了”谁就是最快的那条路。DFS则相当于你先只盯着一个快递站问到天黑问完再打另一个可能第一个就给绕远路了。5.3 如何选择DFS还是BFS一个实用的决策清单我总结了几条经验基本上能应对绝大多数题目和工程场景如果你关心**“从A到B是否存在路径”**DFS/BFS都行DFS代码更简单。如果你关心**“从A到B的最短路径无权图”**必须用BFS。如果你关心**“所有可能的排列/组合/子集”**DFS回溯是最自然的。如果你关心**“拓扑排序”**DFS或BFS都可但BFS的Kahn算法更直观。如果你关心**“图的连通分量”**DFS/BFS都行DFS写起来更短。如果树的深度极大递归DFS容易爆栈用迭代栈或改BFS。如果图宽度极大BFS内存压力会很大DFS可能更省内存但要深入到底。这个清单看起来简单但我真见过不少朋友因为选错搜索方向写了几百行代码仍然超时或死循环。归根结底你要先搞清楚自己要的是“路径”还是“所有方案”。6. 图文流程迷宫从起点到终点的完整搜索过程为了把这两个算法彻底讲透我造一个3x3的小迷宫起点在左上角(0,0)终点在右下角(2,2)0表示墙1表示路1 1 0 0 1 1 0 1 16.1 DFS走迷宫的过程DFS从(0,0)进入(0,0)入栈标记访问。尝试向下走走到(1,0)发现(1,0)是墙0不行尝试向右走走到(0,1)可以。从(0,1)继续尝试向下走走到(1,1)可以。从(1,1)继续尝试向下走到(2,1)可以。从(2,1)继续尝试向下走越界向右走走到(2,2)到达终点。如果你只关心“能不能到终点”DFS在这里很幸运一次就走通了。但注意它走的路径其实是(0,0) - (0,1) - (1,1) - (2,1) - (2,2)长度为4。而实际上BFS会发现一条更短的路径(0,0) - (0,1) - (1,1) - (2,1) - (2,2)在这个例子里两种算法找到的路径一样长但在更复杂的地图上DFS很可能绕远路。这个例子就是想告诉你DFS找到路径不代表最短。6.2 BFS走迷宫的过程BFS从(0,0)出发第一层候选是相邻的(0,1)(1,0)是墙跳过。第二层从(0,1)出发候选是(1,1)。第三层从(1,1)出发候选是(2,1)。第四层从(2,1)出发候选是(2,2)到达终点。因为每层步数比上一层多1所以一旦到达终点就是最短路径。为了直观理解你可以在纸上画一个“层号标注图”0号: (0,0) 1号: (0,1) 2号: (1,1) 3号: (2,1) 4号: (2,2)这个数字标注的过程其实就是BFS在“分层”。我常用这个方法来调试写BFS时打印每个节点的层号一旦发现终点层号不合理地大就说明中间有路径绕路或者漏了某些邻居。6.3 调试排错的实战经验我调试DFS和BFS最常用的技巧是加“痕迹打印”。因为递归和队列执行顺序比较抽象肉眼跟代码容易懵。在关键位置加print打印当前节点、当前栈/队列状态问题一下就暴露了。比如我在写DFS时经常遇到“明明访问过却还是重新进入”的情况。这种情况多半是忘记了visited标记或者标记放在终止条件之后导致没被设置。检查顺序就是越界判断 - visited判断 - 标记visited - 继续递归。BFS里我遇到最多的问题是“队列永远无法清空”——因为你在往队列里塞邻居之前忘记查邻居是否已在队列/已访问。解决办法就是在入队时立刻标记visited而不是在出队时标记。这句“入队即标记”能防止大量重复入队问题我在后面还会再强调一次。7. 经典应用场景DFS和BFS在真实项目里怎么用7.1 连通分量图片区域分割和岛屿计数假设你有一张二值图片1表示陆地0表示海水你想知道有多少块不连通的陆地。这就是经典的“岛屿数量”问题可以同时用DFS或BFS解决。我在做图像连通域标记时思路完全一样遍历每个像素如果发现一个未访问的1就从这个点开始做DFS或BFS把所有邻接的1都标记为访问计数器加1。一次遍历结束计数器就是连通分量数。时间复杂度是O(像素总数)空间复杂度取决于你用的方式。我对大图做连通域更偏好BFS因为递归DFS在大图上容易出现递归过深问题。7.2 拓扑排序任务依赖关系的执行顺序在项目管理、构建系统、数据流编排中任务之间往往存在依赖关系。例如任务B依赖任务A则必须先完成A再执行B。把所有任务排成一个线性序列保证每个任务都在它的依赖之后这就是拓扑排序。DFS方式对每个节点做DFS当一个节点的所有后继节点都访问完成之后把它记录到结果栈中。最后反向输出栈就是拓扑顺序。BFS方式Kahn算法先统计每个节点的入度把所有入度为0的节点入队然后不断出队每出队一个节点就把它所有邻居的入度减1再把新的入度为0的邻居入队。这个过程我在做数据管道调度时经常用直观且不容易错。7.3 状态空间搜索从八数码到拼图游戏DFS和BFS不只用于树的遍历和图的连通性还能用于“状态空间搜索”。比如8数码问题3x3滑块拼图每个状态是棋盘的一种排列相邻状态是移动一次空格后的排列。从初始排列出发搜索目标排列这就是隐式图搜索。我建议用BFS来做这种问题的“最少步数”查询因为你关心的是最短操作序列。DFS在这种问题里会非常糟糕因为状态空间巨大一条路走到黑可能陷入很深的无解分支。这时候可以配合“剪枝”“迭代加深”进一步优化但基础还是DFS/BFS那套框架。7.4 社交网络层级遍历好友推荐和影响力传播在社交网络分析里如果你想知道“你的第2层好友”是谁BFS天然合适。从你出发第一层是你的直接好友第二层是好友的好友排除你自己和直接好友。这个过程就是BFS的按层遍历。我做过一个推荐系统用BFS层数给用户之间的亲近程度打分效果比纯基于距离的计算更合理。DFS在这里就不太合适因为用户关系图很宽DFS会一口气钻到很深的社交关系里去不符合我们“由近到远”的推荐直觉。8. 复杂度优化能不能变成O(n)或O(logn)8.1 剪枝DFS专用“加速器”DFS最常见的问题是会遍历大量无用的分支。剪枝的核心思想是在递归过程中如果发现当前分支继续走下去也不可能找到解就提前返回。这个思想在回溯类问题里极其重要。比如数独求解、N皇后问题不加剪枝和加剪枝的运行时间可能差几个数量级。我常用的剪枝策略有可行性剪枝当前路径明显不满足约束条件时提前return。上限剪枝如果当前已走步数 到目标的理论最小距离 已知最优解就return。重复状态剪枝用哈希表记录已经搜索过的状态避免重复搜索。这个“估价剪枝”的思路本质上就是A算法的基础。虽然A是更进阶的内容但我认为剪枝思维应该从DFS阶段就建立起来。8.2 记忆化搜索DFSDP的结合如果你在递归DFS过程中发现同样子状态会被反复计算很多次这时可以在递归里加一个“备忘录”也就是记忆化搜索。比如计算斐波那契数列的递归版本朴素DFS是O(2^n)加一个数组记录fib(k)的结果就变成O(n)。记忆化搜索在我处理树形DP、区间DP、状态压缩DP时几乎必不可少。它既保留了DFS“天然好写拓扑关系”的优点又通过缓存避免重复计算。这和BFS其实也没冲突——很多动态规划也常用BFS做转移但记忆化搜索确实更像DFS家族的进化形态。8.3 为什么有些问题BFS无法通过优化变成O(n)有些同学会问BFS已经是O(VE)已经是线性时间了还能再优化吗不行了因为你需要至少访问每个节点和每条边一次才能判断它们是什么。这个下界和信息论里的“至少要读一遍输入”是一个道理。但在具体实现里可以通过更好的数据结构比如双端队列、多线程/并行BFS来减少常数不过复杂度阶数不会变。值得注意的是如果图特别大上亿节点O(VE)也不一定能跑完。这时你可能需要换思路比如双向BFS、A*、跳点搜索、甚至层次聚类之类的算法。9. 从DFS/BFS到进阶算法你接下来可以学什么9.1 A*搜索有方向感的“智能BFS”当你做路径规划时BFS虽然能求最短路径但它像无头苍蝇一样全面扩散很浪费。A在BFS基础上加了一个“启发式函数”可以优先扩展“看起来最接近目标”的节点。它兼顾了DFS的“方向感”和BFS的“最优性”是游戏寻路和地图导航的核心算法。理解A之前BFS是最佳的入门跳板。我当时学A时最大的感悟是**A只是把BFS的队列换成了优先队列并按 f(n) g(n) h(n) 排序而已。** 完全可以把A*理解成“有提示的BFS”。9.2 迭代加深DFSDFS和BFS的折衷迭代加深DFS的思路是先限定DFS深度为1做一次深度优先搜没有找到解就限定深度为2再没有就限定深度为3……直到找到解或深度用尽为止。这样做的好处是既节省内存只有栈又能像BFS一样找到最短路径。很多棋类AI的搜索就采用这种方法如国际象棋的极小化极大搜索中常见。这个算法的实现不复杂但能帮你更深刻理解DFS的“深度边界”和BFS的“层序边界”之间的等价关系。9.3 双向BFS、剪枝、并查集……继续扩展从BFS还能扩展出双向BFS、多源BFS从DFS还能扩展出强连通分量Tarjan算法、割点桥、拓扑排序。这些全是基础DFS/BFS的变形。我建议不要急着跳过而是先把今天这篇里的模板反复手写至少5遍直到能闭眼写出来再往进阶走会顺利非常多。10. 新手常见误区与避坑心得10.1 误区一在BFS里用“出队时标记visited”这是我见过最多的问题。如果你只是把节点加入队列但不在入队时标记为已访问那么同一个节点可能会被多个邻居同时入队造成大量重复计算甚至死循环。正确做法是入队时立刻标记visited。我之前在一个共享节点较多的图里犯过这个错导致运行超时排查了整整一个小时。最后打印队列才发现同一个节点反复出现几十次。从此我就记住了这个规则。10.2 误区二DFS递归忘记终止条件有些同学在写递归DFS时总觉得“反正会有边界”然后不写终止条件最后导致栈溢出或无限递归。终止条件必须放在最前面宁可多写几个if return也不要漏掉。尤其在网格DFS里“越界返回”“障碍返回”“已访问返回”这三件套一个都不能少。10.3 误区三认为DFS一定能找到最短路径我见过不少人把DFS当“万能搜索”用结果在迷宫题里得到的路径长度比最优解长很多然后就懵了。记住DFS是“能到”BFS是“最近”。如果题目要求最短路径你就老老实实写BFS别拿DFS硬凑。10.4 实操建议调试时如何打印状态我推荐一个小习惯在写DFS/BFS时先打印“进入节点”和“离开节点”用缩进表示递归深度。这样一旦结果不对你能像看日记一样看出它实际走的方向。BFS则打印每一层队列中的所有元素尤其是节点坐标或节点id。还有一个实用技巧用颜色或数字标记访问层数。我在迷宫调试时会把每个位置到达的步数填进同一个二维数组最终打印出来一眼就能看出哪条路是最短路径。11. 总结与进一步建议DFS和BFS是算法宇宙的“两个原子核”几乎所有搜索问题都能拆解到它们身上。关键不在于背代码而在于理解“栈”和“队列”两种数据结构背后的顺序逻辑理解“回溯”和“分层”两种推进模式的区别。我个人的习惯是拿到一道搜索题先问自己三个问题需要找一条可行路径还是找最短路径前者优先DFS后者优先BFS。是显式图还是隐式图隐式图要特别注意状态去重。递归的深度是否会爆栈会的话用显式栈或BFS。最后再分享一个练习秘诀每天花10分钟在白纸上手画一棵二叉树分别写出DFS前序、中序、后序和BFS层序的节点访问序列。坚持一周你对这两个算法的理解会快速提升。另外如果要做大图搜路别让递归深度超限优先用BFS或迭代版DFS配合一个合理的visited结构比什么都强。说到底算法不是用来背的是用来解决问题的。从这两个最基础的搜索开始把“为什么这样设计”想透彻以后学任何高级算法你都会觉得顺理成章。