天津市网站建设_网站建设公司_改版升级_seo优化

图的广度优先搜索（BFS）详解

广度优先搜索（Breadth-First Search，BFS）是与DFS互补的图遍历算法，核心思想是**“先广后深”**：从起始节点出发，先访问当前节点的所有邻接节点（一层），再依次访问这些邻接节点的邻接节点（下一层），如同“水波扩散”，逐层遍历所有可达节点。

资料：https://pan.quark.cn/s/43d906ddfa1b、https://pan.quark.cn/s/90ad8fba8347、https://pan.quark.cn/s/d9d72152d3cf

一、核心概念

1. 节点状态：同样需标记「未访问」「已访问」，避免重复遍历。
2. 核心数据结构：队列（FIFO），保证“先进先出”，实现逐层访问。
3. 适用场景：最短路径（无权图）、层序遍历、连通分量、判断两点是否可达等。

二、图的存储方式

与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特性与复杂度

1. 时间复杂度：
   • 邻接表：O(V + E)（V为节点数，E为边数），每个节点和边仅处理一次。
   • 邻接矩阵：O(V²)，需遍历每个节点的所有可能邻接节点。
2. 空间复杂度：O(V)（队列存储节点，最坏情况存入所有节点，如完全图）。
3. 核心特点：
   • 保证无权图的最短路径（层数即为最短路径长度）。
   • 按层遍历，适合“扩散式”场景（如社交网络好友推荐）。
   • 迭代实现更自然，无递归栈溢出风险。

七、BFS vs DFS（核心区别）

八、常见应用场景

1. 无权图最短路径（如迷宫最短出口、社交网络最短好友链）。
2. 层序遍历（如二叉树层序遍历、图的分层处理）。
3. 检测图的连通性（无向图连通分量、有向图可达性）。
4. 洪水填充（如图片区域填充、扫雷游戏周边检测）。
5. 拓扑排序（配合入度表，适用于DAG）。