广度优先遍历（BFS）：逐层探索的智慧

引言：什么是广度优先遍历？

广度优先遍历（BFS）是一种用于遍历或搜索树（Tree）和图（Graph）结构的算法。其核心思想是逐层访问节点，先访问离起点最近的节点，再逐步向外扩展。BFS 被广泛应用于最短路径查找、社交网络分析、迷宫求解等领域。本文将通过实例详细解析 BFS 的工作原理、实现方式及其实际应用。

一、BFS 的算法原理

1.1 核心思想：队列与分层遍历

BFS 的关键在于使用**队列（Queue）**这一数据结构。算法步骤如下：

1. 将起点加入队列，并标记为已访问。

2. 循环执行以下操作，直到队列为空：

   • 从队列中取出一个节点（队首元素）。

   • 访问该节点的所有未被访问的邻居节点，依次加入队列并标记为已访问。

通过这种方式，BFS 保证了所有节点按距离起点的层级顺序被访问。

1.2 算法伪代码

def BFS(graph, start):queue = deque([start])  # 初始化队列visited = set([start])  # 记录已访问节点while queue:node = queue.popleft()  # 取出队首节点print(node)  # 处理节点（例如打印）for neighbor in graph[node]:  # 遍历邻居if neighbor not in visited:visited.add(neighbor)queue.append(neighbor)

二、实例解析：BFS 如何工作？

2.1 实例1：二叉树的层次遍历

问题描述：给定一棵二叉树，按层输出所有节点的值（从左到右）。
输入二叉树：

复制

       1/   \2     3/ \   /4   5 6

BFS 过程：

1. 初始队列：[1]，访问第1层：1。

2. 处理节点1，将其子节点2、3入队。队列：[2, 3]，访问第2层：2, 3。

3. 处理节点2，子节点4、5入队。队列：[3, 4, 5]。

4. 处理节点3，子节点6入队。队列：[4, 5, 6]，访问第3层：4, 5, 6。

5. 处理剩余节点（均为叶子节点），队列逐步清空。

输出结果：[[1], [2,3], [4,5,6]]。

代码实现（Python）：

from collections import dequeclass TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef level_order(root):if not root:return []queue = deque([root])result = []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# 测试代码
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
print(level_order(root))  # 输出：[[1], [2, 3], [4, 5, 6]]

2.2 实例2：图的社交网络好友推荐

问题描述：在社交网络中，如何找到某个用户的“二度好友”（好友的好友），并按距离排序？
输入图结构（邻接表表示）：

graph = { 'Alice': ['Bob', 'Charlie'], 'Bob': ['Alice', 'Diana', 'Eve'], 'Charlie': ['Alice', 'Frank'], 'Diana': ['Bob'], 'Eve': ['Bob', 'Grace'], 'Frank': ['Charlie'], 'Grace': ['Eve'] }

BFS 过程（以 Alice 为起点）：

1. 第0层（直接好友）：Bob, Charlie。

2. 第1层（二度好友）：Diana, Eve, Frank（通过 Bob 和 Charlie 访问）。

3. 第2层（三度好友）：Grace（通过 Eve 访问）。

输出结果：

• 二度好友：Diana, Eve, Frank（距离为2）。

代码实现：

from collections import dequedef find_second_degree_friends(graph, start):queue = deque([(start, 0)])  # (节点, 距离)visited = {start: 0}second_degree = []while queue:user, distance = queue.popleft()if distance == 2:second_degree.append(user)for neighbor in graph[user]:if neighbor not in visited:visited[neighbor] = distance + 1queue.append((neighbor, distance + 1))return second_degree# 测试
print(find_second_degree_friends(graph, 'Alice'))  # 输出：['Diana', 'Eve', 'Frank']

2.3 实例3：迷宫最短路径

问题描述：在一个二维矩阵表示的迷宫中（0代表可通行，1代表障碍），求从起点到终点的最短路径。
输入迷宫：

[[0, 1, 0, 0],[0, 0, 0, 1],[0, 1, 0, 0],[0, 0, 0, 0]
]
起点 (0,0)，终点 (3,3)。

BFS 过程：

1. 从起点 (0,0) 开始，向四个方向（上下左右）探索。

2. 逐层记录可达的坐标，并标记已访问。

3. 第一次到达终点 (3,3) 时的路径即为最短路径。

最短路径长度：6步（路径示例：(0,0) → (1,0) → (1,1) → (1,2) → (2,2) → (3,2) → (3,3)）。

代码实现：

from collections import dequedef shortest_path(maze, start, end):rows = len(maze)cols = len(maze[0])directions = [(-1,0), (1,0), (0,-1), (0,1)]  # 上下左右queue = deque([(start[0], start[1], 0)])  # (x, y, 步数)visited = set([(start[0], start[1])])while queue:x, y, steps = queue.popleft()if (x, y) == end:return stepsfor dx, dy in directions:nx, ny = x + dx, y + dyif 0 <= nx < rows and 0 <= ny < cols:if maze[nx][ny] == 0 and (nx, ny) not in visited:visited.add((nx, ny))queue.append((nx, ny, steps + 1))return -1  # 不可达

# 测试
maze = [[0, 1, 0, 0],[0, 0, 0, 1],[0, 1, 0, 0],[0, 0, 0, 0]
]
print(shortest_path(maze, (0,0), (3,3)))  # 输出：6

三、BFS 的应用场景

3.1 最短路径问题

• 无权图的最短路径：BFS 天然保证首次访问到目标节点的路径是最短的（如迷宫问题）。

• 网络路由算法：路由器使用类似 BFS 的算法寻找最短跳数路径。

3.2 社交网络分析

• 好友推荐：查找用户的二度、三度好友。

• 影响力传播模型：模拟信息在社交网络中的扩散过程。

3.3 状态空间搜索

• 八数码问题：通过 BFS 找到从初始状态到目标状态的最少移动次数。

• 游戏 AI（如象棋、围棋）：生成所有可能的走法并评估最优解。

四、BFS 与 DFS 的对比

特性	BFS	DFS
数据结构	队列（Queue）	栈（Stack）
空间复杂度	高（存储所有当前层节点）	低（存储路径上的节点）
适用场景	最短路径、分层遍历	拓扑排序、连通性检测、回溯问题
解的性质	首次找到的解一定最优	可能找到非最优解

---

五、总结

广度优先遍历通过逐层扫描的方式，为解决最短路径、层级关系分析等问题提供了高效的方法。其核心在于队列的先进先出（FIFO）特性，确保节点按距离顺序被处理。无论是社交网络中的好友推荐，还是迷宫中的最短路径查找，BFS 都展现了其强大的实用性。理解 BFS 不仅有助于掌握算法基础，更能培养“分层思考”的编程思维。