13 min read2,668 words

广度优先搜索与层序遍历

简介

广度优先搜索（Breadth-First Search, BFS）是一种用于遍历或搜索树、图等数据结构中所有节点的算法。其核心思想是从起始节点开始，逐层地向外探索，即先访问当前节点的所有相邻节点，然后再访问这些相邻节点的相邻节点，以此类推。这种“由近及远”的探索方式，使得BFS天然地具有“层序”的特性，能够保证在无权图中找到的路径是最短路径。在树结构中，这种逐层访问节点的过程被称为“层序遍历”，是二叉树等结构最基础的遍历方式之一。

BFS算法通常借助队列（Queue）这一先进先出（FIFO）的数据结构来实现。算法将起始节点放入队列，然后循环执行以下操作：从队列头部取出一个节点进行访问，并将其所有未被访问过的相邻节点依次放入队列尾部。这个过程持续到队列为空，意味着所有可达节点都已被访问。BFS的应用极其广泛，从简单的二叉树遍历，到复杂的图论问题如最短路径、连通分量计算、状态空间搜索（如迷宫问题、滑动谜题）等，都是其大显身手的领域。

本章将深入剖析BFS的队列实现与标准层序遍历模板，探讨其在树与图结构中的应用，特别是解决最短路径问题的原理。我们还将介绍两种重要的优化技巧：双向BFS和多源BFS，它们能显著提升在某些特定场景下的搜索效率。最后，通过“二叉树的层序遍历”、“打开转盘锁”和“岛屿数量”这三个经典例题，我们将把理论知识转化为解决实际问题的能力，帮助读者熟练掌握这一强大的算法范式。

核心概念

BFS的核心在于“队列”和“层”的概念。队列保证了节点按照被发现的顺序进行处理，这正是“广度优先”的体现。当我们从队列中处理节点时，我们实际上是在处理当前“层”的所有节点。在处理当前层节点的同时，我们将下一层的节点加入队列，为下一轮迭代做准备。这种机制确保了所有第k层的节点都在第k+1层的节点之前被访问。

在树结构中，层序遍历是BFS的直接应用。对于图结构，BFS需要额外维护一个“已访问”集合（通常使用哈希集合），以防止重复访问节点和陷入循环。BFS求解无权图最短路径的原理基于一个关键性质：当BFS第一次访问到某个节点时，它所经过的路径就是从起点到该节点的最短路径（边数最少）。这是因为BFS是按距离起点由近到远的顺序访问节点的。

为了更直观地理解BFS的扩散过程，我们可以用以下流程图表示其在一个网格中的典型执行流程：

graph TD S["起点 (0,0)"] --> L1_1["第一层: (0,1)"] S --> L1_2["第一层: (1,0)"] L1_1 --> L2_1["第二层: (0,2)"] L1_1 --> L2_2["第二层: (1,1)"] L1_2 --> L2_3["第二层: (1,1)"] L1_2 --> L2_4["第二层: (2,0)"] L2_1 --> L3_1["第三层: ..."] L2_2 --> L3_2["第三层: ..."]

上图展示了从起点(0,0)开始的BFS过程。起点自身构成第0层。第一步，探索其相邻格点(0,1)和(1,0)，它们构成第一层。第二步，分别从第一层的节点出发，探索其相邻节点，形成第二层。注意，节点(1,1)可能从(0,1)或(1,0)两个方向都被发现，但BFS会确保它只被处理一次（通过已访问集合），并且此时记录的距离（层数）就是最短距离2。

实战示例

下面我们通过一个经典的“二叉树层序遍历”问题来展示BFS的标准模板。题目要求：给定一个二叉树的根节点 root ，返回其节点值的层序遍历结果（即逐层地，从左到右访问所有节点）。

from collections import deque
from typing import List, Optional
# 二叉树节点定义
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def levelOrder(root: Optional[TreeNode]) -> List[List[int]]:
"""
二叉树的层序遍历
:param root: 二叉树根节点
:return: 二维列表，每个子列表代表一层的节点值
"""
# 初始化结果列表
result = []
# 如果根节点为空，直接返回空结果
if not root:
return result
# 使用双端队列 deque 作为队列，初始化时将根节点放入
queue = deque([root])
# 当队列不为空时，持续处理
while queue:
# 当前层的节点数量
level_size = len(queue)
# 用于存储当前层所有节点值的列表
current_level = []
# 循环处理当前层的每一个节点
for _ in range(level_size):
# 从队列左侧弹出（取出）一个节点
node = queue.popleft()
# 将节点值加入当前层列表
current_level.append(node.val)
# 如果该节点有左子节点，将其加入队列（即下一层的节点）
if node.left:
queue.append(node.left)
# 如果该节点有右子节点，将其加入队列
if node.right:
queue.append(node.right)
# 将当前层的结果加入到最终结果中
result.append(current_level)
return result
# 示例用法
if __name__ == "__main__":
# 构造一个简单的二叉树: [3,9,20,null,null,15,7]
#       3
#      / \
#     9  20
#        / \
#       15  7
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
# 进行层序遍历
traversal_result = levelOrder(root)
print("二叉树层序遍历结果：")
for i, level in enumerate(traversal_result):
print(f"第{i}层: {level}")
# 输出：
# 第0层: [3]
# 第1层: [9, 20]
# 第2层: [15, 7]

这段代码是BFS层序遍历的经典模板。关键点在于内层的for _ in range(level_size):循环，它确保了在一次外层while循环中，我们只处理当前队列中属于同一“层”的所有节点。在将它们弹出并记录值的同时，将它们的子节点加入队列，这些子节点将在下一次外层循环中被处理。deque的使用保证了popleft()操作的时间复杂度为O(1)，是Python中实现队列的高效选择。

对比分析

BFS与深度优先搜索（DFS）是图遍历的两大基石，它们各有优劣，适用于不同的场景。下面的表格对这两种算法进行了详细的对比。

方案	优势	劣势	适用场景
广度优先搜索 (BFS)	1. 能自然找到无权图的最短路径。 2. 按层遍历，结果直观，易于处理分层逻辑。 3. 对于解空间较“浅”或目标较近的问题，效率高。	1. 空间开销大，队列需要存储当前层的所有节点，在稠密图或宽树上可能消耗大量内存。 2. 对于深度很大但目标在深处的场景，可能不如DFS高效。	1. 层序遍历（二叉树、多叉树）。 2. 最短路径问题（无权图，如迷宫最少步数）。 3. 寻找最近的相关节点（如社交网络中的一度、二度好友）。 4. 状态空间搜索中，当需要最少步骤时（如“打开转盘锁”）。
深度优先搜索 (DFS)	1. 空间开销相对较小，递归栈深度通常与树/图深度成正比。 2. 对于解空间较“深”或需要遍历所有可能路径的问题（如排列组合）很有效。 3. 实现简洁（递归形式）。	1. 找到的路径不一定是最短的。 2. 递归深度过深可能导致栈溢出。 3. 遍历顺序不如BFS直观。	1. 拓扑排序。 2. 检测图中环。 3. 路径查找与回溯（如八皇后、全排列）。 4. 连通分量计算（也可用BFS）。

此外，在BFS内部，根据问题的不同，也有不同的优化策略：

BFS变体	核心思想	适用场景
标准BFS	从单一源点开始逐层扩展。	通用场景，如二叉树遍历、单源最短路径。
多源BFS	初始化时将多个源点同时加入队列，并视为第0层。	多个起点同时扩散的问题，如“腐烂的橘子”、“地图分析”（寻找离陆地最远的海洋）。
双向BFS	从起点和终点同时开始BFS，当两边的搜索相遇时终止。	搜索空间巨大且起点终点明确的问题，能极大减少搜索范围，如“单词接龙”、“打开转盘锁”（优化版）。

最佳实践

始终标记已访问节点（针对图）：在遍历图结构时，必须在节点入队时就将其标记为“已访问”，而不是在出队时。这样可以避免同一个节点被多次加入队列，防止重复工作和可能的无限循环。通常使用一个与队列同步维护的哈希集合（visited_set）或一个与原图结构同尺寸的布尔数组来实现。
使用deque实现队列：在Python中，使用collections.deque作为队列是最佳选择。它的popleft()和append()操作都是近似O(1)的时间复杂度。避免使用列表（list）的pop(0)操作，因为它是O(n)的，会严重影响BFS的性能。
层序遍历时记录层大小：在进行层序遍历（如二叉树）或需要知道当前遍历层数（即距离）时，务必在每一轮循环开始前，通过current_level_size = len(queue)获取当前队列的长度。然后通过一个for循环处理完这current_level_size个节点。这是实现“层”逻辑的关键模式。
考虑双向BFS优化：当搜索空间非常大（如状态数指数级增长），并且已知起点和终点时，优先考虑使用双向BFS。实现时，使用两个队列（或集合）分别从两头扩散，每次选择当前节点数较少的一边进行扩展，直到两边相遇。这能将时间复杂度从O(b^d)降低到O(b^(d/2))，其中b是分支因子，d是起点到终点的距离。
将多源问题转化为单源问题：对于像“多个起点同时扩散”这类问题，不要对每个起点单独运行BFS。技巧是初始化队列时，将所有起点都加入，并视为第0层。这样，BFS的第一轮扩展就相当于所有起点同时走出了第一步，完美地将多源问题纳入了标准BFS框架。

小结

广度优先搜索是一种基于队列、按层遍历数据结构的强大算法。其核心价值在于能够高效地找到无权图中的最短路径，并自然地处理分层逻辑。掌握标准BFS模板、理解其与DFS的差异，是算法学习的基础。在面对具体问题时，应灵活运用多源BFS和双向BFS等优化技巧，以应对大规模搜索空间的挑战。通过“层序遍历”、“打开转盘锁”和“岛屿数量”等经典问题的练习，可以深刻体会BFS在树、图以及状态空间搜索中的广泛应用和变通之道。

下一节：核心数据结构进阶