Python如何实现广度优先搜索BFS_基于collections.deque构建队列-Python教程-PHP中文网

python如何实现广度优先搜索bfs_基于collections.deque构建队列

为什么不用list而要用`deque`实现BFS队列

因为list.pop(0)是O(n)操作，每次从头部弹出都会移动后面所有元素；而deque.popleft()是O(1)，BFS频繁出入队时性能差距会指数级放大。实测10万节点图上，list版本可能卡顿数秒，deque几乎瞬时完成。

常见错误是写成queue = []; queue.pop(0)，尤其新手从循环队列概念直接套用列表索引，结果在稍大规模数据下超时或被判定为算法低效。

必须从collections导入：from collections import deque
初始化写法是queue = deque([start_node])，不是deque(start_node)（后者会把节点拆成字符/元素）
入队统一用append()，出队统一用popleft()——别混用pop()，否则变成DFS行为

`deque`版BFS的标准骨架怎么写

核心就三步：初始化队列、循环取点、对未访问邻居入队。关键在于访问标记必须在入队时做，而不是出队时做，否则同一节点可能被重复加入多次。

from collections import deque
<p>def bfs(graph, start):
visited = set([start])
queue = deque([start])</p><pre class="brush:python;toolbar:false;">while queue:
    node = queue.popleft()
    print(node)  # 处理当前节点

    for neighbor in graph.get(node, []):
        if neighbor not in visited:
            visited.add(neighbor)
            queue.append(neighbor)  # 入队即标记，防重入

注意：graph通常为dict，键是节点，值是邻接节点列表；若用邻接矩阵，遍历逻辑要改为索引扫描，但deque用法不变。

Li Python Sec Check

Python 安全规范检查工具：基于 CloudBase 规范、腾讯安全指南，LLM 智能分析（默认禁用，优先本地执行）

下载

遇到层级遍历（如二叉树层序）怎么改

BFS天然适合分层，关键是每次循环前记录当前队列长度，作为本层节点数。这不是额外开数组，而是利用len(queue)的O(1)特性。

不要在循环中动态查len(queue)，必须在每轮开头固定一次：for _ in range(len(queue)):
如果需要返回每层结果，用level_nodes = []收集本轮node，再result.append(level_nodes)
图结构做层级遍历时，仍需严格维持“入队即标记”，否则跨层重复访问会污染层级边界

示例片段：

while queue:
    level_size = len(queue)
    current_level = []
    for _ in range(level_size):
        node = queue.popleft()
        current_level.append(node)
        for n in graph[node]:
            if n not in visited:
                visited.add(n)
                queue.append(n)