广度优先搜索（BFS）系统分类与经典题型详解

广度优先搜索（Breadth-First Search, BFS） 是一种基于队列实现的层次遍历算法，适用于最短路径、状态转移、连通性等问题。其核心思想是“层层扩展”，从起点出发，逐层访问所有可达节点。

本文从基础概念到经典题型进行系统分类与解析，涵盖从入门到进阶的所有常见问题。

---

一、BFS的三大核心要素

1. ✅ 队列（Queue）：存储待访问节点，保证先进先出（FIFO）的遍历顺序
2. 🧭 已访问标记（Visited）：避免重复访问（如哈希表、二维数组）
3. 🔁 层数统计（Level）：记录当前遍历的层数（用于最短路径问题）

---

二、BFS经典题型分类

1. 树的层次遍历

（1）基础层序遍历

🌳 102. 二叉树的层序遍历

python
展开代码
def levelOrder(root):
    if not root: return []
    queue = collections.deque([root])
    res = []
    while queue:
        level_size = len(queue)
        level = []
        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)
            if node.left: queue.append(node.left)
            if node.right: queue.append(node.right)
        res.append(level)
    return res

（2）变形问题

🌀 103. 二叉树的锯齿形层序遍历

• 关键点：偶数层反转结果（level[::1 if len(res) % 2 == 0 else -1]）

---

2. 图的最短路径

（1）无权图最短路径

📚 127. 单词接龙

• 策略：用 BFS 找从 beginWord 到 endWord 的最短转换序列
• 优化：双向 BFS（从起点和终点同时搜索）

（2）带权图最短路径

🏙️ 1334. 阈值距离内邻居最少的城市

• 变种：Dijkstra 算法（优先队列实现）

---

3. 网格类BFS（岛屿 / 迷宫）

（1）连通区域计数

🏝️ 200. 岛屿数量

python
展开代码
def numIslands(grid):
    if not grid: return 0
    directions = [(-1,0),(1,0),(0,-1),(0,1)]
    m, n = len(grid), len(grid[0])
    count = 0
    
    for i in range(m):
        for j in range(n):
            if grid[i][j] == '1':
                queue = collections.deque([(i,j)])
                grid[i][j] = '0'  # 标记已访问
                while queue:
                    x, y = queue.popleft()
                    for dx, dy in directions:
                        nx, ny = x + dx, y + dy
                        if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == '1':
                            queue.append((nx, ny))
                            grid[nx][ny] = '0'
                count += 1
    return count

（2）最短路径搜索

🧭 1091. 二进制矩阵中的最短路径

• 关键点：8方向遍历，记录层数作为路径长度

---

4. 状态转移问题

（1）数字变换

🔐 752. 打开转盘锁

• 策略：将每个密码（如"0000"）的8种变换（每位±1）加入队列
• 优化：用哈希表快速判断死亡数字

（2）滑动拼图

🧩 773. 滑动谜题

• 关键点：将棋盘状态转化为字符串，记录0的位置和移动方向

---

5. 多源BFS

（1）多起点同时扩散

🧱 542. 01 矩阵

python
展开代码
def updateMatrix(mat):
    m, n = len(mat), len(mat[0])
    queue = collections.deque()
    for i in range(m):
        for j in range(n):
            if mat[i][j] == 0:
                queue.append((i,j))
            else:
                mat[i][j] = -1  # 未访问标记
    
    directions = [(-1,0),(1,0),(0,-1),(0,1)]
    while queue:
        x, y = queue.popleft()
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < m and 0 <= ny < n and mat[nx][ny] == -1:
                mat[nx][ny] = mat[x][y] + 1
                queue.append((nx, ny))
    return mat

（2）腐烂的橘子

🍊 994. 腐烂的橘子

• 同类型：多源 BFS 统计感染轮数

---

三、BFS解题技巧总结

1. 🧭 方向数组：网格问题用 directions = [(-1,0),(1,0),(0,-1),(0,1)] 简化代码
2. 🔁 层数记录：通过 level_size = len(queue) 控制当前层遍历
3. 🧠 状态压缩：将复杂状态（如棋盘）转化为字符串或数字存储
4. ⚡ 双向BFS：当起点和终点明确时，双向搜索可大幅减少时间复杂度

---

四、高频BFS题目列表

类型	经典题目
树遍历	102. 层序遍历、103. 锯齿遍历
图最短路径	127. 单词接龙、1334. 阈值距离城市
网格问题	200. 岛屿数量、1091. 最短路径
状态转移	752. 打开转盘锁、773. 滑动谜题
多源BFS	542. 01矩阵、994. 腐烂橘子

---

五、总结

BFS 的核心在于层次遍历与最短路径搜索。

掌握要点：

1. ✅ 队列控制遍历顺序，确保先访问的节点距离更短
2. 🧱 灵活处理状态（如字符串密码、棋盘布局）
3. 🔀 区分DFS与BFS：DFS适合连通性检测，BFS适合最短路径

---

📌 推荐练习顺序：树的层序遍历 → 网格类问题 → 状态转移 → 多源BFS → 图最短路径