为什么 BFS 能找到最短路径而 DFS 不能为什么 DFS 只需要栈BFS 却需要队列今天我们用最直观的方式把这两种经典遍历算法讲透、讲全。无论是刷 LeetCode 还是做实际开发深度优先遍历DFS和广度优先遍历BFS都是绕不开的基础。但很多同学对它们的理解停留在“会写代码”的层面一旦问到“什么时候用 DFS什么时候用 BFS”就含糊不清。本文将从核心思想、数据结构、空间时间、代码模板、应用场景五个维度把 DFS 和 BFS 彻底讲清楚。全文约 5000 字建议先收藏再慢慢看。一、从一张图开始假设有如下无向图我们从顶点 A 出发遍历A / \ B C / \ \ D E F深度优先DFS一条路走到黑走不通再回头。典型的路线A → B → D → (回溯到 B) → E → (回溯到 A) → C → F。广度优先BFS一层一层往外扩。先访问 A 的邻居 B、C再访问 B、C 的邻居 D、E、F。路线A → B → C → D → E → F。二、核心思想与数据结构维度深度优先遍历DFS广度优先遍历BFS核心思想尽可能深地探索到达叶子或死胡同后回溯从起点开始逐层向外扩展数据结构栈显式或递归调用栈队列实现方式递归隐式栈或手动栈迭代 队列访问顺序沿着一条分支走到黑再换另一条按离起点的距离层数依次访问2.1 DFS 的两种实现递归版最简洁visitedset()defdfs_recursive(node):ifnodeinvisited:returnvisited.add(node)print(node)forneighborinnode.neighbors:dfs_recursive(neighbor)栈版防止递归过深defdfs_stack(start):visitedset()stack[start]whilestack:nodestack.pop()ifnodenotinvisited:visited.add(node)print(node)# 注意入栈顺序影响遍历顺序forneighborinnode.neighbors:ifneighbornotinvisited:stack.append(neighbor)2.2 BFS 的标准实现fromcollectionsimportdequedefbfs(start):visitedset([start])queuedeque([start])whilequeue:nodequeue.popleft()print(node)forneighborinnode.neighbors:ifneighbornotinvisited:visited.add(neighbor)queue.append(neighbor)三、详细异同点对比表对比维度DFSBFS数据结构栈LIFO队列FIFO空间复杂度最坏O(h)h 为图深度递归栈深度。最差 O(V)如链表图O(w)w 为最大层节点数。最差 O(V)如星型图时间复杂度O(VE)邻接表O(VE)邻接表是否找到最短路径不一定找到的第一条路径不保证最短是无权图中第一次访问即为最短步数是否可解无穷图可能无限递归需加深度限制可以只要目标有限内存消耗特点平均较小只存一条路径平均较大存一层所有节点是否可利用递归天然递归结构不适合递归天然迭代典型应用拓扑排序、连通分量、回溯、迷宫生成最短路径、Web 爬虫、层次遍历、连通块四、深入剖析为什么 BFS 能找到最短路径在无权图中BFS 按层扩展起点为第 0 层所有直接邻居为第 1 层以此类推。第一次访问到目标节点时经过的边数一定是最少的因为任何更短的路径都会在更早的层中被访问到。DFS 则没有这种性质它可能先沿着一条长路径走到目标而另一条更短的路径还没探索到。结论在无权图中求最短路径必须用 BFS或 Dijkstra但 BFS 足够。如果图有权值需要使用 Dijkstra 或 A* 等算法。五、实际场景选型指南场景推荐算法理由求无权图最短路径如迷宫最少步数BFS天然保证最短判断图的连通性是否所有节点可达两者都可DFS 代码更短拓扑排序有向无环图DFS后序或 KahnBFSDFS 直观检测环有向图DFS三色标记利用递归栈寻找所有路径路径枚举DFSBFS 会存储大量中间路径爬虫抓取有限深度BFS可控制爬取宽度避免过深棋盘游戏 AI如五子棋DFS带深度限制需要探索分支二叉树的层序遍历BFS按层处理二叉树的前/中/后序遍历DFS天然递归顺序六、代码示例邻接表下的 BFS 与 DFSPythonfromcollectionsimportdequeclassGraph:def__init__(self,num_vertices):self.num_verticesnum_vertices self.adj[[]for_inrange(num_vertices)]# 邻接表defadd_edge(self,u,v):self.adj[u].append(v)self.adj[v].append(u)# 无向图# BFSdefbfs(self,start):visited[False]*self.num_vertices dist[-1]*self.num_vertices# 可选记录最短距离visited[start]Truedist[start]0queuedeque([start])order[]whilequeue:nodequeue.popleft()order.append(node)forneighborinself.adj[node]:ifnotvisited[neighbor]:visited[neighbor]Truedist[neighbor]dist[node]1queue.append(neighbor)returnorder,dist# DFS 递归defdfs_recursive(self,start):visited[False]*self.num_vertices order[]self._dfs_helper(start,visited,order)returnorderdef_dfs_helper(self,node,visited,order):visited[node]Trueorder.append(node)forneighborinself.adj[node]:ifnotvisited[neighbor]:self._dfs_helper(neighbor,visited,order)# DFS 栈迭代defdfs_iterative(self,start):visited[False]*self.num_vertices stack[start]order[]whilestack:nodestack.pop()ifnotvisited[node]:visited[node]Trueorder.append(node)# 按逆序入栈可模拟递归顺序forneighborinreversed(self.adj[node]):ifnotvisited[neighbor]:stack.append(neighbor)returnorder# 测试gGraph(6)edges[(0,1),(0,2),(1,3),(1,4),(2,5)]foru,vinedges:g.add_edge(u,v)print(BFS:,g.bfs(0)[0])# 0,1,2,3,4,5 或 0,2,1,5,3,4取决于邻接表顺序print(DFS递归:,g.dfs_recursive(0))print(DFS迭代:,g.dfs_iterative(0))七、常见误区澄清误区1BFS 一定比 DFS 耗内存不一定。在平衡树中BFS 队里存储最后一层约 V/2DFS 栈深度为树高约 log VDFS 更省。但在星型图中BFS 队列很小第一层后队列只有 1 个节点DFS 栈却可能存储所有节点如一直深度优先走到底→ DFS 更耗内存。所以要根据图结构分析。误区2DFS 必须用递归可以用显式栈避免递归深度过大导致栈溢出Python 默认递归深度 ~1000。对于深度很大的图如长链推荐迭代栈。误区3只能用于图不能用于树树是图的特例同样适用。二叉树的前序、中序、后序遍历是 DFS 的特例层序遍历是 BFS。误区4BFS 不能用于有向图完全可以只需按出边扩展即可。八、图遍历的可视化对比ASCII 艺术初始图 A / \ B C / \ \ D E F 深度优先A→B→D→E→C→F 访问顺序A(0) → B(1) → D(2) → 回溯 → E(3) → 回溯 → C(4) → F(5) 路径形状一条蜿蜒的深谷 广度优先A→B→C→D→E→F 层0A 层1B, C 层2D, E, F 访问顺序像水波扩散。九、总结DFS追求深度用栈适合查找所有路径、拓扑排序、回溯问题。BFS追求广度用队列适合最短路径、层次遍历、连通块分析。时间复杂度均为 O(VE)空间复杂度取决于图结构但 BFS 往往需要更多内存存放一层的节点。选择口诀要最短路径用 BFS要穷举所有解用 DFS。掌握了这两种遍历你就掌握了图算法的半壁江山。如果觉得有帮助欢迎点赞、收藏、转发有任何疑问欢迎评论区留言讨论。本文首发于 CSDN未经授权禁止转载。