BFS（广度优先搜索）算法详解：原理、实现与应用

1. 什么是 BFS？

广度优先搜索（Breadth-First Search，BFS）是一种用于遍历或搜索树或图的算法。它从根节点（或任意节点）开始，逐层地访问所有相邻节点，然后再进入下一层。BFS 的核心思想是“先访问离起点最近的节点”，因此它天然适合解决最短路径问题（在无权图中）。

2. BFS 的核心思想与特点

• 队列（Queue）驱动：BFS 使用队列来存储待访问的节点，遵循先进先出（FIFO）原则。
• 逐层遍历：从起点开始，先访问所有距离为 1 的节点，再访问距离为 2 的节点，依此类推。
• 避免重复访问：通常需要一个 visited 集合（或数组）来标记已访问的节点，防止陷入循环。
• 无权图最短路径：在边权均为 1 的图中，BFS 首次访问到目标节点时经过的路径就是最短路径。

3. BFS 算法步骤（伪代码）

def bfs(graph, start): visited = set() # 记录已访问节点 queue = deque([start]) # 使用双端队列作为队列 visited.add(start) while queue: node = queue.popleft() print(node) # 处理当前节点 for neighbor in graph[node]: if neighbor not in visited: visited.add(neighbor) queue.append(neighbor)

4. BFS 的典型应用场景

• 图的连通性判断：判断两个节点是否连通。
• 无权图最短路径：如迷宫最短路径、单词接龙最短转换序列。
• 层次遍历：二叉树的层序遍历、多叉树的层序输出。
• 扩散问题：如岛屿数量、腐烂的橘子、广播消息传播范围。
• 状态搜索：八数码问题、华容道等状态空间搜索。

5. BFS 与 DFS 的对比

6. 实战示例：二叉树的层序遍历（Java）

public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> result = new ArrayList<>(); if (root == null) return result; Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { int levelSize = queue.size(); List<Integer> level = new ArrayList<>(); for (int i = 0; i < levelSize; i++) { TreeNode node = queue.poll(); level.add(node.val); if (node.left != null) queue.offer(node.left); if (node.right != null) queue.offer(node.right); } result.add(level); } return result; }

7. BFS 的优化与变体

• 双向 BFS：从起点和终点同时开始搜索，相遇时即找到最短路径，大幅减少搜索空间。
• 多源 BFS：初始时将多个源点同时加入队列，用于解决多个起点的扩散问题（如多个腐烂橘子同时扩散）。
• A* 搜索：在 BFS 基础上加入启发式函数，优先搜索最有希望的节点，用于带权图的最短路径。
• 0-1 BFS：使用双端队列，边权为 0 的插入队首，边权为 1 的插入队尾，解决边权只有 0 和 1 的图的最短路径。

8. 常见误区与注意事项

• 忘记标记 visited：会导致重复访问甚至无限循环。
• 队列与层次遍历：需要记录当前层大小时，应在进入循环前获取 queue.size()。
• 空间复杂度：BFS 在最坏情况下需要存储整层的节点，对于分支因子大的图可能内存消耗较大。
• 无权图假设：BFS 只能直接用于无权图的最短路径；带权图需要使用 Dijkstra 等算法。

9. 总结

BFS 是一种基础且强大的图遍历算法，其逐层遍历的特性使其成为解决最短路径、扩散、层次遍历等问题的首选。掌握 BFS 的核心实现（队列 + visited 标记）以及其典型应用场景，是算法学习中的重要一环。在实际编码中，注意边界条件处理、避免重复访问，并可根据问题特点选择双向 BFS、多源 BFS 等优化变体。