1. 为什么每个学图的人都绕不开BFS和DFS把图想象成一张渔网每个绳结是一个节点每段绳子是一条边。我们要在这张网上做最基本的操作——从一个绳结出发把整张网都走一遍这就是图遍历。而BFS广度优先搜索和DFS深度优先搜索就是走这张网的两套完全不同的脚法。面试考、考试考、刷题考连实际工程里做网络爬虫、地图导航、社交推荐都离不开这两种算法。坦白说我见过不少做了两年后端开发的同事聊业务头头是道一问他BFS和DFS的区别只能答出一个用队列一个用栈再深一点就露怯了。原因很简单——大多数人只背了代码模板从没想清楚这两个东西到底是什么、为什么长这样、该怎么选。这篇文章我用具体代码、对比表格和真实排查经验把BFS和DFS从头到尾拆一遍。看完你至少能获得三样东西一是再也不会混淆两种遍历的适用场景二是能默写出两种遍历的通用模板并说清楚每一步在干什么三是知道在实际项目里不是刷题是真实应用怎么用它们解决路径规划、连通性检测、依赖环检测这类问题。2. 从一张图说起先搞懂存储和邻接这两个前提2.1 图的两种存储方式决定了遍历怎么写BFS和DFS是走的算法但走之前你得先把图存下来。工程里最常见的两种存法邻接矩阵和邻接表。邻接矩阵就是一个二维数组matrix[i][j]值为1表示i和j之间有边0表示没有。稠密图边很多用这个查起来最快O(1)就能判断两个节点是否相连。但缺点也明显——假设有10万个节点矩阵就有10万乘以10万个格子光这个二维数组就能把内存撑爆。所以稀疏图边远少于节点数的平方永远优先用邻接表。邻接表是一个数组加链表的组合体graph[i]里存的是一个列表里面是节点i所有直接邻居。在Python里直接用字典套列表就能实现简单到不行graph { A: [B, C], B: [A, D, E], C: [A, F], D: [B], E: [B, F], F: [C, E] }这里graph[A]就是A的所有邻居。这个结构有多常用你去看现有的大规模图计算框架比如处理亿级节点图的引擎底层存储几乎都是邻接表思想的变形。所以本文后面所有遍历代码都基于这种邻接表写法展开。2.2 无向图与有向图遍历时脑子里要有箭头先明确一个基础但特别容易乱的细节无向图的边没有方向A能走到BB也一定能走到A所以邻接表里每个节点的邻居列表互相包含。有向图则有一条条箭头比如微博的关注关系你关注了某大V不代表大V回关了你遍历时不能反向走。写遍历时你得先问自己**这张图是有向还是无向**这决定了visited标记要不要特殊处理。无向图里如果不标记已访问节点BFS/DFS会无限循环在一条边之间反复横跳这是新手最容易踩的坑。等一下多说一句“连通分量”这个概念。在一张无向图里如果从任意节点出发把所有能走到的节点都走完可能还剩下另外一些从哪都走不到的孤立区域这些区域各自是一个连通分量。我们做遍历时其实是在一个连通分量内部打通全部节点。如果整张图有多个连通分量就得分多次启动遍历。这个细节到后面讲图不连通时怎么办还会用到。3. BFS广度优先遍历把扩散想象成水波3.1 从A到GBFS每一步发生了什么BFS的核心逻辑只有一句话从起点出发先访问它所有的邻居再访问邻居的邻居逐层向外推进。想象往平静水面丢一颗石子波纹一圈一圈往外扩——BFS就是那一圈圈的波纹。我画一个简单的图来说明。图长这样A / \ B C / \ \ D E F \ G从A开始BFS访问A把A的邻居B、C放进队列。队列状态[B, C]弹出B访问B把B的邻居D、E放进队列。队列状态[C, D, E]弹出C访问C把C的邻居F放进队列。队列状态[D, E, F]弹出DD没有未访问邻居。队列状态[E, F]弹出E把E的邻居G放进队列。队列状态[F, G]弹出F没有未访问邻居。队列状态[G]弹出G结束。输出顺序是A → B → C → D → E → F → G。注意这里的层级关系A是第一层B和C是第二层D、E、F是第三层G是第四层。这正是BFS最关键的价值——它天然按距离起点由近到远的顺序遍历节点。3.2 BFS的队列实现模板与细节解释直接上代码每行都给出注释from collections import deque def bfs(graph, start): visited set() # 记录已访问节点防止走回头路 queue deque([start]) # 队列谁进队谁就是待处理 visited.add(start) # 起点要立刻标记否则可能被重复入队 while queue: node queue.popleft() # 弹出队首节点 print(node, end ) # 处理当前节点 for neighbor in graph[node]: if neighbor not in visited: visited.add(neighbor) # 入队前就标记这点很重要 queue.append(neighbor) # 邻居入队等待后续处理三个细节非常关键第一为什么是入队时标记visited而不是弹出时标记如果你在弹出时才标记一个节点可能被多个邻居同时发现然后多次入队。一旦这张图比较大队列里会堆积大量重复节点。我一直强调入队即标记谁先进了队后面谁就别想再进队了。第二为什么用deque而不是普通的Python列表普通列表做pop(0)操作的时间复杂度是O(n)因为弹出第一个元素后后面所有元素都要往前挪一位。deque是双端队列两端进出都是O(1)。图如果很大这个差距会变成秒级和分钟级的差距。第三BFS能用来找最短路径在每条边权重一样的前提下。因为它是逐层扩散的第一次搜索到目标节点时走过的边数一定是最少的。这也是为什么迷宫最短步数这类题几乎都是BFS的天下。比如上面那张图从A到GBFS第一次碰到G时路径就是A→B→E→G一共3条边没有比这更短的走法。3.3 迷宫最短路径BFS经典实战举一道很典型的题给定一个m x n网格0表示可通过1表示障碍求从左上角到右下角的最短步数。思路就是把每个格子当成图中的一个节点上下左右相邻且可走的格子互为邻居。为了避免像上面那样手工建一个邻接表可以直接在网格上做BFS每次向四个方向扩展。from collections import deque def shortest_path(grid): rows, cols len(grid), len(grid[0]) visited [[False] * cols for _ in range(rows)] queue deque([(0, 0, 0)]) # (行, 列, 已走路程) visited[0][0] True directions [(-1, 0), (1, 0), (0, -1), (0, 1)] # 上下左右 while queue: r, c, step queue.popleft() if (r, c) (rows - 1, cols - 1): return step for dr, dc in directions: nr, nc r dr, c dc if (0 nr rows and 0 nc cols and not visited[nr][nc] and grid[nr][nc] 0): visited[nr][nc] True queue.append((nr, nc, step 1)) return -1 # 永远走不到终点这个代码里我最想强调的不是方向数组而是入队前检查越界和障碍这份判断逻辑一定要在入队前完成否则非法坐标入了队后面判断会非常痛苦代码也乱。4. DFS深度优先遍历一条路走到黑撞了南墙就回头4.1 和BFS对比DFS到底深在哪如果说BFS是地毯式搜索那DFS就是一条路走到黑。还是上面那张图A / \ B C / \ \ D E F \ GDFS从A开始策略是往一个方向的邻居一直走走到没有未访问邻居为止然后回退到上一个节点尝试另一条分支。比如先从A走到B再从B走到DD没有未访问邻居了回退到BB还有邻居E走到EE还没走完往G走G没邻居了回退到EE也没其他邻居了回退到BB也没了回退到AA还有邻居C走到C再去F。DFS的一种输出顺序是A → B → D → E → G → C → F。注意这个顺序不是唯一的取决于你遍历邻居的顺序代码里邻居列表本身就是有顺序的。但无论顺序怎么变一条路走到黑再回头的核心策略永远不会变。4.2 递归版DFS模板简单但小心爆栈递归版是最好写的也是最难出错的。因为系统帮你自动维护了一个调用栈每次递归调用栈帧里天然记录了当前走到哪个节点下一层递归返回后回退的动作由调用栈完成。代码长这样def dfs_recursive(graph, node, visited): visited.add(node) print(node, end ) for neighbor in graph[node]: if neighbor not in visited: dfs_recursive(graph, neighbor, visited)调用方式visited set() dfs_recursive(graph, A, visited)递归版最大的隐患在深图上。如果这张图是一条长链比如10万个节点串成一串递归深度就到10万层Python默认递归深度限制一般是1000直接抛RecursionError。刷题时数据规模小无所谓但在真实项目里处理图数据比如依赖树层级很深千万别无脑用递归。工程上遇到深图需要把递归转成显式栈用迭代版DFSdef dfs_iterative(graph, start): visited set() stack [start] visited.add(start) while stack: node stack.pop() print(node, end ) for neighbor in graph[node]: if neighbor not in visited: visited.add(neighbor) stack.append(neighbor)注意迭代版的输出顺序和递归版不一定一模一样。原因在于栈是后进先出邻居被压入栈后会倒序弹出。这不算错两种方式都是合法的DFS只是先走哪个邻居的策略不同。做题时不用纠结输出顺序是否一致只要符合DFS的深度优先精神就行。4.3 判断有向图中是否存在环DFS的一个杀手级应用DFS在实际开发里非常有价值的一个场景是检测有向图里有没有环。比如项目管理中A任务依赖BB依赖CC又依赖A那就死锁了。这个检测业务上用DFS最自然。思路是DFS遍历时给每个节点一个状态0表示未访问1表示在当前的递归链路上2表示已经完成搜索。如果你沿着递归往下走遇到一个状态是1的节点说明你又回到了当前这条路线上那就是有环。# 0未访问, 1访问中(还在递归栈上), 2已结束 def has_cycle(graph): state {node: 0 for node in graph} def dfs(node): state[node] 1 for neighbor in graph[node]: if state[neighbor] 1: return True if state[neighbor] 0 and dfs(neighbor): return True state[node] 2 return False for node in graph: if state[node] 0: if dfs(node): return True return False这里状态1的设计不是随便写的。visited的布尔值在这里不够用因为你需要区分在当前的递归链路上和已经搜索完毕的节点。如果只是记录访问过那个节点可能是前面的某个分支里访问完的跟当前路径没有关系误判环的风险就来了。我第一次在实际项目里写这个检测时就吃过漏判的亏只用了一个数组标记是否访问过结果遇到A→B、C→B这种交叉依赖时B被标记访问了但从C再走到B时没报环实际场景里却会因为别的原因出现无限循环。后来改成三色标记法才彻底解决。5. 一张对比表看清BFS和DFS的适用边界5.1 核心差异速查对比维度BFS广度优先DFS深度优先核心数据结构队列先进先出栈后进先出或递归空间复杂度O(W)W是最大层的节点数O(H)H是最大深度长链图可能很大最短路径问题边权相同时天然最优需要枚举所有路径效率低是否适合找连通性适合但不常用天然适合是否适合路径枚举/回溯不适合适合环检测需要拓扑排序配合三色标记法直接做到达解的步骤数第一次到达即为最少步数第一次到达不保证最优空间复杂度值得说透。BFS的队列大小取决于某一层的宽度。如果图是扇形展开BFS会瞬间占用很大内存。DFS的栈大小取决于递归能走多深。如果图是一条长链DFS反而会栈很深。没有谁一定比谁省内存得看图的结构。5.2 实际场景下怎么选一个优秀标的判断流程我总结了一套选型思路要求最短路径/最少步数吗要→选BFS。需要把所有路径都枚举出来吗要→选DFS。图是判定连通性/是否有孤立节点吗两者都行但DFS代码更短。递归深度是否可能超过系统限制可能→改用DFS显式栈或改BFS。图非常宽比如一个节点连了几十万个其他节点吗要警惕BFS的队列爆炸但一般图不会这么离谱真遇到了可以考虑DFS。举几个具体例子。社交网络中六度分隔你和任意陌生人之间不超过6条关系链求的是最短关系路径明显是BFS。游戏里AI走迷宫找出口同样BFS。但八皇后问题数独求解列举所有可能的排列组合每一个都是DFS回溯因为要穷举所有解。再比如搜索引擎的网页爬虫通常用BFS从种子URL逐层抓取这样能保证在相对较浅的层次发现更多新链接。但查一个页面里某个资源是否可到达DFS可能更快因为奔着最深的方向搜索可能一下就找到了。6. 基于图论拓扑排序一种很容易被忽视的BFS/DFS延伸6.1 拓扑排序为什么也归在这两个遍历上有向无环图DAG里有一个特别重要的操作叫拓扑排序把图中所有节点排成一个线性序列使得对于任意一条有向边A→BA都排在B前面。你可以理解为先完成前置依赖再处理后续任务。拓扑排序有两种经典实现恰好一个就是BFS思想Kahn算法一个是DFS思想。Kahn算法的步骤是统计所有节点的入度有向图中有几个节点指向自己。把所有入度为0的节点加入队列。弹出队首节点把它指向的所有邻居的入度减1如果某个邻居入度变成0就加入队列。重复直到队列为空。如果最终处理节点数少于总节点数说明图里有环。用BFS写的Kahn算法逻辑极清晰工程里我最常用它因为还能顺便把环检测给做了from collections import deque def topological_sort(graph): indegree {node: 0 for node in graph} for node in graph: for neighbor in graph[node]: indegree[neighbor] indegree.get(neighbor, 0) 1 queue deque([n for n in graph if indegree[n] 0]) result [] while queue: node queue.popleft() result.append(node) for neighbor in graph[node]: indegree[neighbor] - 1 if indegree[neighbor] 0: queue.append(neighbor) if len(result) ! len(graph): return None # 有环无法拓扑排序 return result基于DFS的拓扑排序也很简单在DFS的回溯阶段也就是一个节点的所有邻居都搜索完之后把节点追加到结果列表头部最后整个列表就是拓扑排序。这里提一句DFS的结束时间戳反序就得到了拓扑序。你品一下这个结论背后的直觉是——一个节点只有在它依赖的所有节点都结束之后才结束所以先结束的排在后面反一下正好就是依赖顺序。这个对应关系理解透了很多图和图计算框架里的深度优先生成树相关概念也会顺手很多。6.2 实际项目中我会刻意用拓扑排序检测循环依赖做微服务架构改造时最大的噩梦之一就是服务A依赖B、B依赖C、C又依赖A编译部署的时候直接卡死。这时候把服务之间的依赖关系建一张有向图跑一次拓扑排序如果返回None就能精准报告存在环。我实际跑过的最大一张依赖图有上万个节点Kahn算法跑这个规模在毫秒级性能完全不是问题。7. 刷题和工程中最容易踩的五个深坑7.1 visited标记的时机问题前面提过入队入栈时标记而不是弹出时标记。这个坑我见过太多次尤其是在网格类迷宫题里。如果你在弹出节点时才标记visited同样一个格子可以被四面八方同时发现入队多次队列膨胀甚至影响最终判断。好习惯只有一个只要节点进入容器队列/栈就立刻标为已访问。7.2 有向图千万别反向遍历有向图中方向很重要。A指向B不代表B指向A。在邻接表里A的邻居列表里有B但B的邻居列表里不一定有A。所以代码遍历时只走graph[node]不要想当然认为可以反向。我自己调试过一次无向图迁移到有向图的代码漏改这个细节结果跑出来一堆幽灵路径。7.3 递归深度的隐性爆栈工程上处理层级很深的图比如文件目录树、组织架构树递归深度很容易撞到Python的1000层限制。小图感觉不到压力测试一上来就RecursionError。解决方案有两个方向调大sys.setrecursionlimit治标不治本深层递归还会拖慢速度或者改用显式栈的迭代版推荐。7.4 网格类图的坐标越界检查BFS/DFS用于二维网格时坐标判断顺序同样很讲究。一定要先判断是否越界再判断是否障碍物再查visited最后才是入队。顺序反了轻则数组越界异常重则用到已经没有意义的坐标值判断障碍逻辑混乱。可以看看上面的迷宫代码条件顺序是清晰的三段式越界 → 访问状态 → 障碍。7.5 图不连通时遍历会漏掉孤立节点这是最后一个也是新手最常掉进去的坑。如果你只从某一个起点跑BFS/DFS而整张图有多个连通分量那么从起点走不到的那些节点根本不会被访问。处理方案是对每个节点循环启动遍历visited set() for node in graph: if node not in visited: bfs(graph, node) # 或 dfs这也就是前面提过的外层套一层循环保证所有连通分量都被覆盖。判断一个图是否连通这个问题没有这层外层循环答案一定错。8. 结语在我自己的代码里BFS和DFS是怎么选出来的写到最后分享一点纯粹个人的工程视角。我做过的图相关项目里BFS和DFS从来不是死记硬背的选择它们背后其实是两个完全不同的思维模式BFS是海平面上升均匀推进DFS是钻头下探回退再探。你真正内化了这套直觉后看很多题目和业务需求的第一反应就会变成选型而不是搜模板。给你一个实用的参考习惯凡是从A到B最少要几步类问题先写BFS凡是有哪些走法、组合有哪些类问题先写DFS加回溯。两者的复杂度分析中BFS的空间一般是广度峰值DFS的空间一般是深度峰值哪个峰值更小哪个就更稳妥。如果还不放心先去数据规模上判断——节点足够多、层次足够深的场景尽量别用纯递归DFS。最后再补充一个小技巧做BFS时如果怕起点发现多个邻居导致队列重复你可以用一个双端标记法——入队时确实标记visited但如果你既想抓到路径顺序又想保留层数信息可以在队列里存(node, parent)或者(node, depth)。这种队列里多带一个字段的习惯对实现记录最短路径完整路线按层打印节点这类需求的时候特别省事。回头你拿了这些代码去跑一张真实的依赖关系图再把两种遍历的访问顺序各自打印出来看一下你对广度和深度的理解一定比背任何模板都扎实。