数据结构与算法 / 系统课时
广度优先搜索
广度优先搜索
广度优先搜索按照“离起点的边数从少到多”扩展顶点。本课使用队列完成遍历,并在第一次发现顶点时记录距离与前驱,从而在无权图中恢复一条最短路径。
学习目标
- 理解队列为何能保证按层访问顶点。
- 使用
visited、distance和parent记录遍历状态。 - 在无权图中计算最短距离并恢复具体路径。
知识导图
广度优先搜索
├── 初始化
│ ├── 起点入队
│ ├── 标记已访问
│ └── 距离设为 0
├── 分层扩展
│ ├── 队首出队
│ ├── 扫描邻接点
│ └── 未访问顶点入队
└── 最短路径
├── distance 记录边数
├── parent 记录前驱
└── 从终点反向恢复路径问题背景或应用场景
社交关系中的“最少经过几个人”、网格地图中的“最少移动次数”、依赖网络中的“最少跳数”,都可以抽象为无权图最短路径。这里的“无权”表示每条边的代价相同,因此只需比较经过的边数。
BFS 也是后续学习拓扑层次、二分图判定和多源最短路的基础。它与深度优先搜索的主要差异不在于是否访问所有顶点,而在于待处理顶点的组织方式:BFS 使用先进先出的队列。
核心原理
队列中始终保存已经发现、但邻接边尚未全部扫描的顶点。起点距离为 0;当距离为 的顶点出队时,新发现的邻接点距离一定为 。由于队列先进先出,距离更小的顶点总会先被处理。

对于邻接表表示的图,每个顶点最多入队一次,每条边最多被扫描一次,因此时间复杂度为 ,额外空间复杂度为 。若使用邻接矩阵,扫描每个顶点的整行,时间复杂度会变为 。
首次发现某个顶点时必须立即标记已访问,而不是等它出队后再标记。这样可以防止同一顶点被多个前驱重复加入队列。
基础用法
一次标准 BFS 可以按以下顺序执行:
- 将所有距离初始化为
-1,表示尚不可达。 - 将起点加入
ArrayDeque,同时设置distance[start] = 0。 - 每次取出队首顶点,依次扫描其邻接点。
- 对尚未访问的邻接点设置距离和前驱,并立即入队。
- 需要路径时,从终点沿
parent反向回溯,再将结果反转。
distance[target] == -1 表示终点与起点不连通。起点到自身的最短距离为 0,恢复出的路径只包含起点。
完整可运行示例
下面的 Java 17 程序构造一个无向图,从顶点 A 开始遍历,并输出到 F 的最短路径。将代码保存为 BFSShortestPathDemo.java。
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Deque;
import java.util.List;
public class BFSShortestPathDemo {
private static final String[] LABELS = {"A", "B", "C", "D", "E", "F"};
private static final class Result {
private final List<Integer> order;
private final int[] distance;
private final int[] parent;
private Result(List<Integer> order, int[] distance, int[] parent) {
this.order = order;
this.distance = distance;
this.parent = parent;
}
}
public static void main(String[] args) {
List<List<Integer>> graph = createGraph(LABELS.length);
addUndirectedEdge(graph, 0, 1);
addUndirectedEdge(graph, 0, 2);
addUndirectedEdge(graph, 1, 3);
addUndirectedEdge(graph, 2, 3);
addUndirectedEdge(graph, 2, 4);
addUndirectedEdge(graph, 3, 5);
addUndirectedEdge(graph, 4, 5);
Result result = bfs(graph, 0);
System.out.println("BFS order: " + formatVertices(result.order));
System.out.println("Distances from A:");
for (int vertex = 0; vertex < LABELS.length; vertex++) {
System.out.println(LABELS[vertex] + " = " + result.distance[vertex]);
}
List<Integer> path = buildPath(result.parent, result.distance, 0, 5);
System.out.println("Shortest path A -> F: " + formatPath(path));
}
private static Result bfs(List<List<Integer>> graph, int start) {
int vertexCount = graph.size();
int[] distance = new int[vertexCount];
int[] parent = new int[vertexCount];
java.util.Arrays.fill(distance, -1);
java.util.Arrays.fill(parent, -1);
Deque<Integer> queue = new ArrayDeque<>();
List<Integer> order = new ArrayList<>();
// 入队时立即标记,保证每个顶点最多进入队列一次。
distance[start] = 0;
queue.addLast(start);
while (!queue.isEmpty()) {
int current = queue.removeFirst();
order.add(current);
for (int next : graph.get(current)) {
if (distance[next] != -1) {
continue;
}
distance[next] = distance[current] + 1;
parent[next] = current;
queue.addLast(next);
}
}
return new Result(order, distance, parent);
}
private static List<Integer> buildPath(
int[] parent, int[] distance, int start, int target) {
if (distance[target] == -1) {
return Collections.emptyList();
}
List<Integer> reversed = new ArrayList<>();
for (int current = target; current != -1; current = parent[current]) {
reversed.add(current);
if (current == start) {
break;
}
}
Collections.reverse(reversed);
return reversed;
}
private static List<List<Integer>> createGraph(int vertexCount) {
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < vertexCount; i++) {
graph.add(new ArrayList<>());
}
return graph;
}
private static void addUndirectedEdge(
List<List<Integer>> graph, int first, int second) {
graph.get(first).add(second);
graph.get(second).add(first);
}
private static String formatVertices(List<Integer> vertices) {
List<String> labels = new ArrayList<>();
for (int vertex : vertices) {
labels.add(LABELS[vertex]);
}
return String.join(" ", labels);
}
private static String formatPath(List<Integer> path) {
if (path.isEmpty()) {
return "unreachable";
}
List<String> labels = new ArrayList<>();
for (int vertex : path) {
labels.add(LABELS[vertex]);
}
return String.join(" -> ", labels);
}
}编译并运行:
javac BFSShortestPathDemo.java
java BFSShortestPathDemo预期输出
BFS order: A B C D E F
Distances from A:
A = 0
B = 1
C = 1
D = 2
E = 2
F = 3
Shortest path A -> F: A -> B -> D -> F邻接点的存储顺序可能改变遍历顺序以及被选中的具体最短路径,但不会改变最短距离。示例中 B 先于 C 被扫描,因此 D 的前驱被记录为 B。
Tips
- Java 中优先使用
ArrayDeque实现队列,避免LinkedList的额外节点开销。 - 多次从不同起点执行 BFS 时,可以复用图结构,但每次都要重新初始化距离和前驱数组。
- 只需要最短距离时可以不保存
parent;只需要判断是否可达时,可以在发现目标后提前结束。 - 多个起点同时入队且距离都设为 0,可以得到“到最近起点的距离”。
常见错误
1. 出队后才标记访问
错误表现是同一顶点被重复入队,队列膨胀,前驱也可能被反复覆盖。正确做法是在设置距离和前驱的同一时刻完成访问标记。
2. 将 BFS 用于一般加权图
BFS 只保证边权相同情况下的最短路径。若边权为非负但不全相同,应使用 Dijkstra 算法;若边权只包含 0 和 1,可使用 0-1 BFS。
3. 忘记处理不可达终点
直接沿 parent 回溯可能得到错误路径或陷入无效访问。恢复路径前应先检查 distance[target] 是否为 -1。
本课练习
- 在示例图中新增顶点 G,并连接 C-G、G-F。要求输出从 A 到所有顶点的距离,验收条件是 G 的距离为 2。
- 修改程序,使其接收任意起点和终点;当终点不可达时输出
unreachable,且不得抛出异常。 - 实现多源 BFS:同时以 A 和 F 为起点,计算每个顶点到最近起点的距离,并验证 D 的距离为 1。
本课总结
- BFS 依靠先进先出的队列按距离层次扩展顶点。
- 在首次发现顶点时记录
distance与parent,即可得到无权图最短距离和具体路径。 - 邻接表实现的 BFS 时间复杂度为 ,并能通过
-1距离识别不可达顶点。
下一课预告
下一课将学习“深度优先搜索”,比较递归与显式栈两种实现,并用发现、完成状态刻画搜索过程。