广度优先遍历 BFS 和深度优先遍历 DFS 适合解决什么问题?

核心考点

图的两种基本遍历策略、实现结构及典型应用场景，重点区分“最短/层次扩展”和“深入探索/回溯枚举”。

参考答案(答题要点)

1.BFS 基本思想：从起点出发，按层次由近及远访问结点，通常借助队列实现。先访问所有距离为1的结点，再访问距离为2的结点，依次扩展。

2.BFS 适合解决的问题：无权图或边权相同的单源最短路径、最少步数问题、层次遍历、判断连通性、求连通分量、判断二分图等。核心优势是第一次到达某结点时，路径长度通常最短。

3.DFS 基本思想：从起点出发，沿一条路径尽可能深入，走不通再回退，通常借助递归或栈实现。类似树的先序遍历。

4.DFS 适合解决的问题：连通性判断、求连通分量、拓扑排序、判断有向图是否有环、求强连通分量、割点与桥、回溯搜索、枚举所有路径或方案等。核心优势是适合深入探索和回退枚举。

5.复杂度：邻接表存储时，BFS 和 DFS 时间复杂度均为 O(V+E);邻接矩阵存储时均为 O(V^2)。BFS 空间主要来自队列，最坏 O(V);DFS 空间主要来自递归栈，最坏 O(V)。

6.总结：看到“最少步数、无权最短路径、层次扩展”优先想 BFS;看到“连通性、拓扑、环、强连通、回溯枚举”优先想 DFS。二者都需设置访问标记，避免重复访问。

易错提醒

BFS 不能直接求带权图的最短路径，带权最短路径常用 Dijkstra 等算法。DFS 不保证得到最短路径。BFS 和 DFS 的遍历序列不唯一，取决于起始点和邻接点的访问顺序。BFS 用队列，DFS 用栈或递归，不要混淆。

今日小测

在无权图中求从顶点 A 到顶点 B 的最少边数，应优先采用哪种遍历?为什么?

答案：优先采用 BFS。因为 BFS 按层次由近及远扩展，第一次访问到 B 时的路径边数最少。