Python实现BFS的遍历结果与手动推演不符，原因何在？

核心问题出在Python的集合（set）是无序数据结构，它不会保证元素的遍历顺序和你定义时的顺序一致。

你的代码里，图的邻接表用了set来存储每个顶点的相邻节点，比如'A': {'B', 'C'}。手动推演时你默认会先处理B再处理C，但实际运行时，Python遍历这个set的顺序可能是C在前、B在后——这直接影响了队列的入队顺序，最终导致遍历结果和你预期的不一样。

具体执行流程对比 #

• 手动推演的假设逻辑：

  1. 初始队列：[A] → 出队A，加入B、C到队列 → 队列变为[B,C]
  2. 出队B，加入D、E → 队列变为[C,D,E]
  3. 出队C，加入F → 队列变为[D,E,F]
     以此类推得到A,B,C,D,E,F。

• 代码实际执行逻辑：

  1. 初始队列：[A] → 出队A，遍历graph['A']的set时顺序是C、B → 队列变为[C,B]
  2. 出队C，遍历graph['C']得到F → 队列变为[B,F]
  3. 出队B，遍历graph['B']得到D、E → 队列变为[F,D,E]
  4. 出队F，其邻接节点均已访问 → 队列变为[D,E]
  5. 依次出队D、E，最终输出A,C,B,F,D,E。

如何得到固定顺序的BFS结果 #

如果需要和手动推演一致的固定顺序，把邻接表的set改成有序结构（比如列表list）即可。比如将：

graph = {'A': {'B', 'C'},
        'B': {'A', 'D', 'E'},
        'C': {'A', 'F'},
        'D': {'B'},
        'E': {'B', 'F'},
        'F': {'C', 'E'}}

改为：

graph = {'A': ['B', 'C'],
        'B': ['A', 'D', 'E'],
        'C': ['A', 'F'],
        'D': ['B'],
        'E': ['B', 'F'],
        'F': ['C', 'E']}

这样每次遍历邻接节点时都会按照你定义的顺序来，就能得到预期的A,B,C,D,E,F。

内容的提问来源于stack exchange，提问作者Shreeya Sharma