BFS（广度优先搜索）
Breadth-First Search，广度优先搜索，是图遍历的两种基本方式之一。
核心思想
从起点开始，先访问所有距离为 1 的节点，再访问距离为 2 的节点，以此类推。就像水波一样一层层扩散。
类比：湖面投石，涟漪一圈圈向外扩散。
代码框架
// 图的 BFS 遍历框架
void traverse(Graph graph, int s, boolean[] visited) {
Queue<Integer> q = new LinkedList<>();
q.offer(s);
visited[s] = true;
while (!q.isEmpty()) {
int cur = q.poll();
System.out.println("visit " + cur);
for (Edge e : graph.neighbors(cur)) {
if (!visited[e.to]) {
visited[e.to] = true;
q.offer(e.to);
}
}
}
}
关键特性
| 特性 | 说明 |
|---|---|
| 数据结构 | 队列（Queue） |
| 遍历顺序 | 广度优先，一层层扩散 |
| visited 数组 | 入队时标记（而非出队时），防止重复入队 |
| 适用场景 | 最短路径（无权图）、层级遍历、社交网络好友推荐 |
BFS 与最短路径
BFS 能保证首次到达某个节点时，走过的路径是最短的（仅适用于无权图或权值相同的图）。
原因：BFS 按距离层级扩散，第一次碰到目标节点时，经过的边数最少。
BFS 算法框架
BFS 算法有三种常见写法：
- 简单写法：适用于简单图遍历，局限性大
- 常用写法（最常用）：记录步数，适合求解最短路径问题
- 灵活写法：适用于复杂状态管理的问题
常用框架（带步数记录）：
int bfs(int s, int target) {
boolean[] visited = new boolean[graph.size()];
Queue<Integer> q = new LinkedList<>();
q.offer(s);
visited[s] = true;
int step = 0;
while (!q.isEmpty()) {
int sz = q.size();
for (int i = 0; i < sz; i++) {
int cur = q.poll();
if (cur == target) return step;
for (int to : neighborsOf(cur)) {
if (!visited[to]) {
q.offer(to);
visited[to] = true;
}
}
}
step++;
}
return -1;
}
双向 BFS 优化
核心思想：从起点和终点同时开始扩散，当两边有交集时停止。
优势：比传统单向 BFS 更快，因为搜索空间增长速度是指数级的，双向搜索可以更快相遇。
局限性：
- 必须知道终点位置才能使用
- 如二叉树最小深度问题，终点（最近的叶子节点）位置未知，无法使用
实现要点：
- 使用哈希集合（而非队列），方便快速判断交集
- 每次选择元素数量少的集合进行扩散，减少搜索空间
- 在计算出邻居节点时就判断是否到达终点
参见：BFS框架（双向 BFS 完整代码示例）
与树层序遍历的关系
图的 BFS 本质上是N叉树遍历基础的延伸：
- 树层序遍历不需要
visited数组（树无环） - 图层序遍历必须加
visited数组（图可能有环，防止重复入队）
二叉树层序遍历与 BFS 的关系
BFS 算法属于遍历思路，关注层级扩散：
- 层序遍历 = BFS 在二叉树上的应用
- 使用队列实现，一层层遍历节点
- BFS 适合求无权图的最短路径
参见：二叉树系列算法核心纲领、层序遍历
时间复杂度
$O(E + V)$，其中：
- $E$ = 边的总数
- $V$ = 节点的总数
BFS 与最短路径算法
BFS 是保证首次到达某个节点时路径最短（仅适用于无权图或权值相同的图）。
基于此拓展的经典算法：
- Dijkstra 算法：BFS + 贪心思想，处理带权重图的最短路径（不能处理负权重）
- A* 算法：BFS + 启发式函数，点对点最短路径的优化（不能处理负权重）
来源
- DFS和BFS的适用场景（首次提及）
- 图遍历基础（第2次提及）
- 二叉树系列算法核心纲领（第3次提及，添加层序遍历关系）
- BFS框架（第4次提及，补充算法框架和双向BFS）