一、什么是广度优先遍历（BFS）？
广度优先遍历（Breadth-First Search，简称 BFS）是一种层级展开的搜索策略。
其核心思想是：先访问当前层的所有节点，再访问下一层的节点。常借助队列（Queue）实现，保证先入先出，按层推进。
二、BFS 的应用场景
| 应用场景 | 描述 |
| 树的层序遍历 | 从上到下、从左到右访问所有节点 |
| 图的最短路径 | 在无权图中找起点到终点的最短路径 |
| 二维数组搜索（如迷宫） | 最少步数、感染扩散、岛屿问题 |
| 多源 BFS | 同时从多个起点扩展，如火焰蔓延 |
三、BFS vs DFS 的区别
| 特性 | BFS（广度优先） | DFS（深度优先） |
| 访问方式 | 一层一层遍历 | 一条路走到底 |
| 实现结构 | 队列（FIFO） | 栈或递归（LIFO） |
| 找最短路径 | 是（无权图/网格） | 否（不能保证最短） |
| 空间复杂度 | O(w)，w为最宽层节点数 | O(h)，h为最大深度 |
四、BFS 在树结构中的应用：层序遍历
示例：层序遍历二叉树
type TreeNode struct { Val int Left *TreeNode Right *TreeNode }
Go 实现（按层收集每层元素）
func levelOrder(root *TreeNode) [][]int { var result [][]int if root == nil { return result } queue := []*TreeNode{root} for len(queue) > 0 { size := len(queue) level := []int{} for i := 0; i < size; i++ { node := queue[0] queue = queue[1:] level = append(level, node.Val) if node.Left != nil { queue = append(queue, node.Left) } if node.Right != nil { queue = append(queue, node.Right) } } result = append(result, level) } return result }
示例输入：
// 构建如下树： // 1 // / \ // 2 3 // / \ \ // 4 5 6 root := &TreeNode{Val: 1} root.Left = &TreeNode{Val: 2} root.Right = &TreeNode{Val: 3} root.Left.Left = &TreeNode{Val: 4} root.Left.Right = &TreeNode{Val: 5} root.Right.Right = &TreeNode{Val: 6} fmt.Println(levelOrder(root)) // 输出：[[1], [2,3], [4,5,6]]
五、BFS 在图结构中的应用：最短路径
我们以无向图为例，从起点出发，寻找所有节点的最短路径长度。
图结构定义：
type Graph struct { adj map[int][]int } func NewGraph() *Graph { return &Graph{adj: make(map[int][]int)} } func (g *Graph) AddEdge(u, v int) { g.adj[u] = append(g.adj[u], v) g.adj[v] = append(g.adj[v], u) // 无向图 }
BFS 实现最短路径（起点到所有点）
func BFSShortestPaths(g *Graph, start int) map[int]int { dist := make(map[int]int) visited := make(map[int]bool) queue := []int{start} dist[start] = 0 visited[start] = true for len(queue) > 0 { node := queue[0] queue = queue[1:] for _, neighbor := range g.adj[node] { if !visited[neighbor] { dist[neighbor] = dist[node] + 1 visited[neighbor] = true queue = append(queue, neighbor) } } } return dist }
示例调用：
g := NewGraph() g.AddEdge(1, 2) g.AddEdge(1, 3) g.AddEdge(2, 4) g.AddEdge(3, 5) g.AddEdge(4, 5) dist := BFSShortestPaths(g, 1) fmt.Println(dist) // 输出每个节点到1的最短路径长度
六、BFS 在二维数组上的应用：最短路径 or 感染扩散
经典问题：迷宫最短路径
type Point struct { X, Y int } func bfsMaze(grid [][]int, start, end Point) int { if grid[start.X][start.Y] == 1 { return -1 } m, n := len(grid), len(grid[0]) visited := make([][]bool, m) for i := range visited { visited[i] = make([]bool, n) } dirs := []Point{{-1, 0}, {1, 0}, {0, -1}, {0, 1}} queue := []Point{start} visited[start.X][start.Y] = true steps := 0 for len(queue) > 0 { size := len(queue) for i := 0; i < size; i++ { curr := queue[0] queue = queue[1:] if curr == end { return steps } for _, d := range dirs { nx, ny := curr.X+d.X, curr.Y+d.Y if nx >= 0 && ny >= 0 && nx < m && ny < n && grid[nx][ny] == 0 && !visited[nx][ny] { visited[nx][ny] = true queue = append(queue, Point{nx, ny}) } } } steps++ } return -1 }
七、复杂度分析
- • 时间复杂度：O(n)
n 为图中节点数（或矩阵中格子数） - • 空间复杂度：O(n)
用于存储访问状态、队列
八、典型题目举例（LeetCode）
| 题目 | 描述 |
| LeetCode 102 层序遍历 | 二叉树的层级展开 |
| LeetCode 200 岛屿数量 | 类似 BFS 求二维图中连通区域 |
| LeetCode 542 01矩阵 | 多源 BFS 计算每个 1 到最近 0 的距离 |
| LeetCode 752 打开转盘锁 | 最少步数解锁问题 |
九、常见问题与调试技巧
- • ❗ 队列顺序不能乱，要始终保证 FIFO（先进先出）
- • ❗ 图结构必须标记访问状态，避免重复访问
- • ✔ BFS 是解决“最少步数”问题的首选
- • ✔ 多源同时扩展，用多个起点一起入队即可
十、总结
| 项目 | 内容说明 |
| 算法类型 | 广度优先搜索 |
| 核心结构 | 队列（Queue） |
| 最适用问题 | 最短路径、层序遍历、感染传播问题 |
| 数据结构支持 | 树、图、二维数组（网格） |
| 空间复杂度 | O(n) |
