图的广度优先搜索（BFS）算法原理与实现

一、描述
广度优先搜索（Breadth-First Search, BFS）是一种用于遍历或搜索图（或树）的经典算法。它的核心思想是从一个起始节点开始，逐层向外探索，先访问所有相邻节点，再依次访问这些相邻节点的未访问邻居，直到遍历完所有可达节点。BFS常用于求解最短路径（无权图）、连通性检测、层级遍历等问题。BFS通常借助队列（FIFO结构）实现，确保先发现的节点先被访问。

二、解题过程循序渐进讲解
假设我们有一个无向图，用邻接表表示，起始节点为s。目标是通过BFS遍历所有节点，并记录每个节点的访问顺序和距离。

步骤1：理解图的数据结构
图可以用邻接表存储，例如：

• 节点0的邻居：1, 2
• 节点1的邻居：0, 3, 4
• 节点2的邻居：0, 5, 6
• 等等

步骤2：BFS核心思路

1. 从起始节点开始，将其标记为已访问，并放入队列。
2. 循环执行以下操作，直到队列为空：
   a. 从队列头部取出一个节点。
   b. 访问该节点的所有邻居，如果邻居未被访问，则标记为已访问，并将其加入队列尾部。

这个过程保证了节点按照与起始节点的距离（边数）递增的顺序被访问。

步骤3：详细步骤分解
以起始节点s=0为例：

1. 初始化：
   • 队列queue = []
   • 访问标记visited = {节点: 布尔值}，全部设为False
   • 距离dist = {节点: 距离}，起始节点距离为0
2. 将节点0标记为已访问，距离设为0，并入队：queue = [0]
3. 队列非空，取出队首节点0：
   • 遍历节点0的邻居[1, 2]：
     • 邻居1未访问，标记为已访问，距离设为dist[0]+1=1，入队。
     • 邻居2未访问，标记为已访问，距离设为dist[0]+1=1，入队。
   • 此时队列为[1, 2]
4. 取出节点1：
   • 遍历邻居[0, 3, 4]：
     • 节点0已访问，跳过。
     • 邻居3未访问，标记为已访问，距离设为dist[1]+1=2，入队。
     • 邻居4未访问，标记为已访问，距离设为dist[1]+1=2，入队。
   • 队列变为[2, 3, 4]
5. 重复此过程，直到队列为空。最终所有节点按距离递增顺序被访问。

步骤4：算法实现（Python示例）

from collections import deque

def bfs(graph, start):
    visited = {node: False for node in graph}
    dist = {node: 0 for node in graph}
    queue = deque([start])
    visited[start] = True
    result = []  # 存储访问顺序

    while queue:
        node = queue.popleft()
        result.append(node)
        for neighbor in graph[node]:
            if not visited[neighbor]:
                visited[neighbor] = True
                dist[neighbor] = dist[node] + 1
                queue.append(neighbor)
    return result, dist

# 示例图（邻接表）
graph = {
    0: [1, 2],
    1: [0, 3, 4],
    2: [0, 5, 6],
    3: [1],
    4: [1],
    5: [2],
    6: [2]
}
order, distances = bfs(graph, 0)
print("BFS访问顺序:", order)  # 例如 [0, 1, 2, 3, 4, 5, 6]
print("各节点距离:", distances)  # 距离从0开始

步骤6：时间复杂度与空间复杂度

• 时间复杂度：O(V + E)，其中V是节点数，E是边数。每个节点和每条边都被处理一次。
• 空间复杂度：O(V)，用于存储队列、访问标记和距离。

步骤7：BFS的应用场景

1. 无权图的最短路径：BFS保证首次访问节点时的距离是最短距离。
2. 连通性检测：遍历所有节点，标记连通分量。
3. 层级遍历：树或图的按层遍历（如二叉树层次遍历）。
4. 网络爬虫：按层级抓取网页链接。
5. 迷宫求解：在二维网格中寻找最短路径。

三、总结
BFS是一种基于队列的图遍历算法，其逐层扩展的特性使其天然适合求解最短路径问题。理解队列在BFS中的作用、访问标记的必要性（避免重复访问和无限循环）以及距离记录的方法是掌握BFS的关键。通过调整数据结构（如记录路径、多源BFS等），BFS可以灵活应用于多种实际问题。