图的广度优先搜索（BFS）

1. 问题描述
广度优先搜索（BFS）是一种用于遍历或搜索图（或树）的算法，其核心思想是按层级逐层访问节点：从起点开始，先访问所有直接相邻的节点（第一层），再访问这些相邻节点的相邻节点（第二层），以此类推。BFS常用于求解最短路径问题（无权图）、连通性判断等场景。

2. 核心思想与关键概念

• 队列（Queue）的作用：BFS使用队列来存储待访问的节点，确保先进入的节点先被访问（FIFO原则），从而实现按层遍历。
• 访问标记（Visited）：为避免重复访问或陷入循环，需记录已访问过的节点。
• 层级扩散：从起点开始，每访问一层节点，将其未访问的邻居加入队列，直到队列为空。

3. 算法步骤详解
假设图以邻接表形式存储，起点为节点 s：

步骤1：初始化

• 创建一个队列 queue，将起点 s 加入队列。
• 创建一个集合 visited（如哈希表或数组），标记 s 为已访问。

步骤2：循环处理队列

• 当队列非空时，重复以下操作：
  1. 出队：从队列中取出队首节点 u。
  2. 访问节点：对 u 执行目标操作（如记录路径、判断是否到达终点等）。
  3. 遍历邻居：检查 u 的所有未访问邻居节点 v：
     • 标记 v 为已访问（防止重复入队）。
     • 将 v 加入队列。

步骤3：终止条件

• 队列为空时，说明所有从起点可达的节点已被访问。

4. 示例演示
以下图为例（无向图，节点编号0~4）：

0 — 1
|   |
2 — 3
 \  |
   4

从节点0开始BFS：

• 初始：队列 [0]，visited {0}。
• 第1步：出队0，访问0；邻居1、2未访问，入队并标记。队列 [1, 2]，visited {0,1,2}。
• 第2步：出队1，访问1；邻居0（已访问）、3（未访问），入队3。队列 [2, 3]，visited {0,1,2,3}。
• 第3步：出队2，访问2；邻居0（已访问）、3（已访问）、4（未访问），入队4。队列 [3, 4]，visited {0,1,2,3,4}。
• 第4步：出队3，访问3；邻居1、2、4（均已被访问），无新节点入队。队列 [4]。
• 第5步：出队4，访问4；邻居2、3（已访问），队列空。

遍历顺序：0 → 1 → 2 → 3 → 4（按层扩散）。

5. 代码实现（伪代码）

def BFS(graph, start):
    queue = collections.deque([start])  # 队列初始化
    visited = set([start])             # 访问标记
    
    while queue:
        u = queue.popleft()           # 出队
        print(u)                      # 访问节点（示例操作）
        for v in graph[u]:            # 遍历邻居
            if v not in visited:
                visited.add(v)
                queue.append(v)       # 邻居入队

6. 应用场景与变体

• 最短路径：在无权图中，BFS首次到达目标节点的路径一定是最短的（边数最少）。
• 连通性判断：通过BFS遍历节点数可判断图的连通分量。
• 扩展功能：记录每个节点的前驱节点可重构路径；记录层数可计算距离。

注意：若图有权重，需使用Dijkstra算法；若需高效判断连通性，也可用并查集。