一文说尽深度遍历和广度遍历：从原理到实战，彻底搞懂图的两大搜索算法
为什么 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 的两种实现
递归版（最简洁）：
visited=set()defdfs_recursive(node):ifnodeinvisited:returnvisited.add(node)print(node)forneighborinnode.neighbors:dfs_recursive(neighbor)栈版（防止递归过深）：
defdfs_stack(start):visited=set()stack=[start]whilestack:node=stack.pop()ifnodenotinvisited:visited.add(node)print(node)# 注意：入栈顺序影响遍历顺序forneighborinnode.neighbors:ifneighbornotinvisited:stack.append(neighbor)2.2 BFS 的标准实现
fromcollectionsimportdequedefbfs(start):visited=set([start])queue=deque([start])whilequeue:node=queue.popleft()print(node)forneighborinnode.neighbors:ifneighbornotinvisited:visited.add(neighbor)queue.append(neighbor)三、详细异同点对比表
| 对比维度 | DFS | BFS |
|---|---|---|
| 数据结构 | 栈（LIFO） | 队列（FIFO） |
| 空间复杂度（最坏） | O(h)，h 为图深度（递归栈深度）。最差 O(V)（如链表图） | O(w)，w 为最大层节点数。最差 O(V)（如星型图） |
| 时间复杂度 | O(V+E)（邻接表） | O(V+E)（邻接表） |
| 是否找到最短路径 | 不一定（找到的第一条路径不保证最短） | 是（无权图中，第一次访问即为最短步数） |
| 是否可解无穷图 | 可能无限递归（需加深度限制） | 可以（只要目标有限） |
| 内存消耗特点 | 平均较小（只存一条路径） | 平均较大（存一层所有节点） |
| 是否可利用递归 | 天然递归结构 | 不适合递归（天然迭代） |
| 典型应用 | 拓扑排序、连通分量、回溯、迷宫生成 | 最短路径、Web 爬虫、层次遍历、连通块 |
四、深入剖析：为什么 BFS 能找到最短路径？
在无权图中，BFS 按层扩展：起点为第 0 层，所有直接邻居为第 1 层，以此类推。第一次访问到目标节点时，经过的边数一定是最少的，因为任何更短的路径都会在更早的层中被访问到。
DFS 则没有这种性质：它可能先沿着一条长路径走到目标，而另一条更短的路径还没探索到。
结论：在无权图中求最短路径，必须用 BFS（或 Dijkstra，但 BFS 足够）。如果图有权值，需要使用 Dijkstra 或 A* 等算法。
五、实际场景选型指南
| 场景 | 推荐算法 | 理由 |
|---|---|---|
| 求无权图最短路径（如迷宫最少步数） | BFS | 天然保证最短 |
| 判断图的连通性（是否所有节点可达） | 两者都可 | DFS 代码更短 |
| 拓扑排序（有向无环图） | DFS（后序）或 Kahn（BFS） | DFS 直观 |
| 检测环（有向图） | DFS（三色标记） | 利用递归栈 |
| 寻找所有路径（路径枚举） | DFS | BFS 会存储大量中间路径 |
| 爬虫抓取（有限深度） | BFS | 可控制爬取宽度，避免过深 |
| 棋盘游戏 AI（如五子棋） | DFS（带深度限制） | 需要探索分支 |
| 二叉树的层序遍历 | BFS | 按层处理 |
| 二叉树的前/中/后序遍历 | DFS | 天然递归顺序 |
六、代码示例：邻接表下的 BFS 与 DFS（Python）
fromcollectionsimportdequeclassGraph:def__init__(self,num_vertices):self.num_vertices=num_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]=0queue=deque([start])order=[]whilequeue:node=queue.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:node=stack.pop()ifnotvisited[node]:visited[node]=Trueorder.append(node)# 按逆序入栈可模拟递归顺序forneighborinreversed(self.adj[node]):ifnotvisited[neighbor]:stack.append(neighbor)returnorder# 测试g=Graph(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))七、常见误区澄清
误区1：BFS 一定比 DFS 耗内存
不一定。在平衡树中，BFS 队里存储最后一层（约 V/2），DFS 栈深度为树高（约 log V），DFS 更省。但在星型图中，BFS 队列很小（第一层后队列只有 1 个节点），DFS 栈却可能存储所有节点（如一直深度优先走到底）→ DFS 更耗内存。所以要根据图结构分析。
误区2：DFS 必须用递归
可以用显式栈，避免递归深度过大导致栈溢出（Python 默认递归深度 ~1000）。对于深度很大的图（如长链），推荐迭代栈。
误区3：只能用于图，不能用于树
树是图的特例，同样适用。二叉树的前序、中序、后序遍历是 DFS 的特例，层序遍历是 BFS。
误区4：BFS 不能用于有向图
完全可以，只需按出边扩展即可。
八、图遍历的可视化对比（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）： 层0：A 层1：B, C 层2：D, E, F 访问顺序像水波扩散。九、总结
- DFS追求深度，用栈，适合查找所有路径、拓扑排序、回溯问题。
- BFS追求广度，用队列，适合最短路径、层次遍历、连通块分析。
- 时间复杂度均为 O(V+E)，空间复杂度取决于图结构，但 BFS 往往需要更多内存存放一层的节点。
- 选择口诀：要最短路径用 BFS，要穷举所有解用 DFS。
掌握了这两种遍历，你就掌握了图算法的半壁江山。
如果觉得有帮助，欢迎点赞、收藏、转发～
有任何疑问，欢迎评论区留言讨论。
本文首发于 CSDN，未经授权禁止转载。