广度优先算法python代码详解

<think> 我们被要求提供广度优先算法（BFS）的Python代码并详细解释。根据引用[1][2][3]，我们知道BFS是一种图遍历算法，它从根节点开始，逐层遍历图中的节点。在二叉树中，BFS就是层次遍历；在图中，BFS会先访问一个节点的所有邻居节点，然后再访问邻居的邻居。 我们将以一个图为例来实现BFS。图可以用邻接表来表示。我们假设图是无向的，并且节点由数字表示。 步骤： 1. 初始化：选择一个起始节点，将其放入队列（通常用队列，先进先出）并标记为已访问。 2. 当队列不为空时： a. 从队列中取出一个节点（队首节点）。 b. 访问该节点（比如打印）。 c. 遍历该节点的所有邻居节点：如果邻居节点未被访问过，则将其加入队列并标记为已访问。 注意：为了避免同一个节点被多次访问，我们需要一个集合（或列表）来记录已访问的节点。 下面我们给出一个使用邻接表表示图的BFS代码，并详细解释。 </think> 以下是对广度优先搜索（BFS）算法的 Python 实现及详细解释： ### 广度优先搜索算法 Python 实现 ```python from collections import deque def bfs(graph, start): """ 广度优先搜索算法实现 参数: graph: 图的邻接表表示，格式为字典 {节点: [邻居列表]} start: 开始遍历的起始节点 """ visited = set() # 创建已访问节点集合 queue = deque([start]) # 创建队列并将起始节点加入队列 visited.add(start) # 标记起始节点为已访问 while queue: # 当队列不为空时循环 node = queue.popleft() # 取出队列最前面的节点 print(node, end=" ") # 访问当前节点 # 遍历当前节点的所有邻居 for neighbor in graph[node]: if neighbor not in visited: visited.add(neighbor) # 标记邻居为已访问 queue.append(neighbor) # 将邻居加入队列尾部 # 示例图的邻接表表示 graph = { 'A': ['B', 'C'], 'B': ['A', 'D', 'E'], 'C': ['A', 'F'], 'D': ['B'], 'E': ['B', 'F'], 'F': ['C', 'E'] } # 从"A"节点开始执行BFS print("BFS遍历顺序:") bfs(graph, 'A') # 输出: A B C D E F ``` ### 代码详细解释 1. **队列数据结构** `deque` 是 Python 中的双端队列，用于实现先进先出（FIFO）结构。BFS 使用队列确保按层级顺序访问节点[^1]。 $$ \text{队列}: [start] \rightarrow \text{处理顺序} $$ 2. **访问标记机制** `visited` 集合记录已访问节点，避免重复访问和无限循环。核心规则：节点加入队列前必须标记为已访问[^2]。 3. **算法流程详解** - **初始化**：起始节点加入队列并标记为已访问 - **循环处理**： a. 取出队列前端节点作为当前节点 b. 访问该节点（示例中打印节点值） c. 遍历所有未访问邻居： - 标记为已访问 $$ \text{visited.add(neighbor)} $$ - 加入队列尾部 $$ \text{queue.append(neighbor)} $$ 4. **遍历特性** - **层级扩展**：优先访问起始节点的所有直接邻居，再访问邻居的邻居 - **最短路径**：首次访问某节点时经历的路径即最短路径（无权图）[^3] - **时间复杂度**：$O(V+E)$，其中 $V$ 为顶点数，$E$ 为边数 5. **示例图遍历过程** ``` 队列状态 访问顺序 已访问集合 [A] A {A} [B,C] B {A,B} [C,D,E] C {A,B,C} [D,E,F] D {A,B,C,D} [E,F] E {A,B,C,D,E} [F] F {A,B,C,D,E,F} ``` ### 应用场景 1. 最短路径查找（社交网络好友关系） 2. 迷宫求解（最少步数） 3. 网络爬虫层级抓取 4. 连通分量检测 5. 广播网络路由算法