广度优先搜索（BFS）
BFS 的关键不是“队列”本身，而是它保证按距离从近到远扩展，所以第一次到达一个点时路径就已经最短。
定义
**广度优先搜索（Breadth-First Search, BFS）**是一种图遍历算法，按照距离起点的层次逐层访问节点，先访问距离近的节点。
图的BFS遍历:
1
/ \
2 3
/ \ \
4 5 6
BFS顺序: 1 → 2 → 3 → 4 → 5 → 6
核心思路
- 层次遍历：按照距离起点的层次逐层访问
- 队列结构：使用队列实现先进先出
- 访问标记：使用visited集合避免重复访问
- 最短路径：在无权图中保证找到最短路径
🎞️ 层序遍历动画
（附件 bfs-layer-traversal.gif 未随站点发布）
观察重点
节点在入队时就标记为已发现，避免同一节点被多个父节点重复加入队列。队列先进先出的顺序保证距离更近的节点先被处理。
为什么无权最短路优先想到 BFS
因为在无权图里，每走一条边的代价都一样。
- 第 0 层：起点
- 第 1 层：一步能到的点
- 第 2 层：两步能到的点
所以某个节点第一次被访问到时，走到它的边数一定最少。
复杂度分析
| 指标 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(V+E) | V是顶点数，E是边数 |
| 空间复杂度 | O(V) | 队列空间 |
| 最坏情况 | O(V+E) | 遍历所有节点和边 |
Go 代码
Go 实现
package main
// BFS基础实现
func BFS(graph [][]int, start int) []int {
visited := make(map[int]bool)
result := []int{}
queue := []int{start}
visited[start] = true
for len(queue) > 0 {
node := queue[0]
queue = queue[1:]
result = append(result, node)
for _, neighbor := range graph[node] {
if !visited[neighbor] {
visited[neighbor] = true
queue = append(queue, neighbor)
}
}
}
return result
}
// BFS最短路径
func BFSShortestPath(graph [][]int, start, target int) []int {
if start == target {
return []int{start}
}
visited := make(map[int]bool)
type QueueItem struct {
node int
path []int
}
queue := []QueueItem{{start, []int{start}}}
visited[start] = true
for len(queue) > 0 {
item := queue[0]
queue = queue[1:]
for _, neighbor := range graph[item.node] {
if !visited[neighbor] {
newPath := append([]int{}, item.path...)
newPath = append(newPath, neighbor)
if neighbor == target {
return newPath
}
visited[neighbor] = true
queue = append(queue, QueueItem{neighbor, newPath})
}
}
}
return nil
}
// BFS最短距离
func BFSShortestDistance(graph [][]int, start int) map[int]int {
distance := make(map[int]int)
queue := []int{start}
distance[start] = 0
for len(queue) > 0 {
node := queue[0]
queue = queue[1:]
for _, neighbor := range graph[node] {
if _, exists := distance[neighbor]; !exists {
distance[neighbor] = distance[node] + 1
queue = append(queue, neighbor)
}
}
}
return distance
}思路展开
BFS的执行过程
以下图为例：
1
/ \
2 3
/ \
4 5
BFS执行过程：
- 初始化：队列=[1]，访问节点1
- 第1层：处理节点1，将邻接节点2、3加入队列
- 第2层：处理节点2，将邻接节点4加入队列
- 第2层：处理节点3，将邻接节点5加入队列
- 第3层：处理节点4（无新邻接节点）
- 第3层：处理节点5（无新邻接节点）
- 完成遍历
访问顺序：1 → 2 → 3 → 4 → 5
BFS vs DFS
| 特性 | BFS | DFS |
|---|---|---|
| 数据结构 | 队列 | 栈/递归 |
| 遍历方式 | 层次遍历 | 深度优先 |
| 最短路径 | ✅ 保证找到 | ❌ 不保证 |
| 空间复杂度 | O(V) | O(V) |
| 适用场景 | 最短路径、层次问题 | 路径查找、连通性 |
易错点
BFS 最大的坑通常不是逻辑复杂，而是访问标记放错时机。
- 最稳的写法是“入队就标记”。
- 如果图不连通，想遍历全图要从每个未访问点重新启动 BFS。
- 存路径时不要对每个节点都整条复制，真正大图里更常用
parent反推路径。 - 有权图不能直接套普通 BFS。
经典题目
优缺点
优点
- ✅ 保证找到最短路径（无权图）
- ✅ 适合层次遍历问题
- ✅ 可以处理多源BFS
- ✅ 不会栈溢出
缺点
- ❌ 空间消耗可能较大（宽度大时）
- ❌ 不适合深度很大的图
- ❌ 无法直接处理有权图
相关主题
- DFS - 深度优先的替代方案
- BFS基础模板 - 更通用的模板页
- Dijkstra算法 - 有权图的最短路径
- 岛屿数量 - BFS应用
- 图算法 - 返回图算法总览