图的广度优先搜索（BFS）详解
广度优先搜索（Breadth-First Search，BFS）是与DFS互补的图遍历算法，核心思想是**“先广后深”**：从起始节点出发，先访问当前节点的所有邻接节点（一层），再依次访问这些邻接节点的邻接节点（下一层），如同“水波扩散”，逐层遍历所有可达节点。
资料：https://pan.quark.cn/s/43d906ddfa1b、https://pan.quark.cn/s/90ad8fba8347、https://pan.quark.cn/s/d9d72152d3cf
一、核心概念
- 节点状态：同样需标记「未访问」「已访问」，避免重复遍历。
- 核心数据结构：队列（FIFO），保证“先进先出”，实现逐层访问。
- 适用场景：最短路径（无权图）、层序遍历、连通分量、判断两点是否可达等。
二、图的存储方式
与DFS一致，优先使用邻接表（稀疏图效率更高），下文均以邻接表为例实现。
三、基础BFS实现（迭代）
1. 算法步骤
- 初始化队列，将起始节点入队，并标记为已访问。
- 循环：若队列非空，出队队首节点，处理该节点（如输出）。
- 遍历该节点的所有邻接节点：若未访问，则标记为已访问并入队。
- 重复直到队列为空。
注：BFS极少用递归实现（递归本质是栈，与BFS的队列逻辑冲突），因此仅讲迭代版。
2. 代码实现（Python）
fromcollectionsimportdequedefbfs(graph,start):""" 广度优先搜索（无权图） :param graph: 邻接表表示的图（字典/列表） :param start: 起始节点 :return: 遍历顺序列表 """visited=set()# 记录已访问节点queue=deque([start])# 初始化队列，存入起始节点visited.add(start)# 标记起始节点为已访问result=[]whilequeue:# 出队队首节点node=queue.popleft()result.append(node)# 处理节点（加入结果）# 遍历所有邻接节点forneighboringraph[node]:ifneighbornotinvisited:visited.add(neighbor)# 标记为已访问（避免重复入队）queue.append(neighbor)# 入队returnresult# 示例：无向图（邻接表）if__name__=="__main__":# 图结构：0-1-3/4，0-2graph={0:[1,2],1:[0,3,4],2:[0],3:[1],4:[1]}print("BFS遍历结果：")print(bfs(graph,0))3. 输出结果
BFS遍历结果： [0, 1, 2, 3, 4]解释：从0出发，先访问第一层（0），再访问第二层（1、2），最后访问第三层（3、4），符合“逐层扩散”的特性。
四、处理非连通图
若图包含多个连通分量（无向图），需遍历所有节点，对未访问的节点启动BFS：
fromcollectionsimportdequedefbfs_connected_components(graph):""" BFS遍历非连通图，返回所有连通分量 :param graph: 邻接表表示的图 :return: 各连通分量的遍历结果列表 """visited=set()components=[]fornodeingraph:ifnodenotinvisited:# 对每个未访问节点启动BFSqueue=deque([node])visited.add(node)component=[node]whilequeue:curr_node=queue.popleft()forneighboringraph[curr_node]:ifneighbornotinvisited:visited.add(neighbor)queue.append(neighbor)component.append(neighbor)components.append(component)returncomponents# 示例：非连通图if__name__=="__main__":# 两个连通分量：0-1-2 和 3-4graph={0:[1],1:[0,2],2:[1],3:[4],4:[3]}print("\n非连通图的连通分量（BFS）：")print(bfs_connected_components(graph))输出结果
非连通图的连通分量（BFS）： [[0, 1, 2], [3, 4]]五、BFS经典应用：无权图最短路径
BFS的核心优势是能高效求解无权图中两点的最短路径（层数即为最短路径长度），只需在遍历中记录每个节点的前驱/距离：
fromcollectionsimportdequedefbfs_shortest_path(graph,start,end):""" 求解无权图中start到end的最短路径 :param graph: 邻接表 :param start: 起始节点 :param end: 目标节点 :return: 最短路径列表（无路径返回None） """ifstart==end:return[start]visited=set([start])queue=deque([(start,[start])])# 队列存储(当前节点, 路径)whilequeue:node,path=queue.popleft()forneighboringraph[node]:ifneighbor==end:returnpath+[neighbor]# 找到终点，返回完整路径ifneighbornotinvisited:visited.add(neighbor)queue.append((neighbor,path+[neighbor]))returnNone# 无可达路径# 示例调用if__name__=="__main__":graph={0:[1,2],1:[0,3,4],2:[0],3:[1],4:[1]}print("\n0到4的最短路径：")print(bfs_shortest_path(graph,0,4))# 输出 [0, 1, 4]六、BFS特性与复杂度
- 时间复杂度：
- 邻接表：O(V + E)（V为节点数，E为边数），每个节点和边仅处理一次。
- 邻接矩阵：O(V²)，需遍历每个节点的所有可能邻接节点。
- 空间复杂度：O(V)（队列存储节点，最坏情况存入所有节点，如完全图）。
- 核心特点：
- 保证无权图的最短路径（层数即为最短路径长度）。
- 按层遍历，适合“扩散式”场景（如社交网络好友推荐）。
- 迭代实现更自然，无递归栈溢出风险。
七、BFS vs DFS（核心区别）
| 特性 | 广度优先搜索（BFS） | 深度优先搜索（DFS） |
|---|---|---|
| 核心数据结构 | 队列（FIFO） | 栈（递归/手动栈） |
| 遍历顺序 | 逐层遍历（横向） | 深度优先（纵向） |
| 最短路径 | 可求无权图最短路径 | 无法保证最短路径 |
| 空间复杂度 | 最坏O(V)（队列） | 最坏O(V)（递归栈） |
| 适用场景 | 最短路径、层序遍历 | 路径查找、环检测、拓扑排序 |
八、常见应用场景
- 无权图最短路径（如迷宫最短出口、社交网络最短好友链）。
- 层序遍历（如二叉树层序遍历、图的分层处理）。
- 检测图的连通性（无向图连通分量、有向图可达性）。
- 洪水填充（如图片区域填充、扫雷游戏周边检测）。
- 拓扑排序（配合入度表，适用于DAG）。
