求BFS与拓扑排序结果不同的图的邻接表

在有向无环图（DAG）中，拓扑排序的结果并不唯一，而基于Kahn算法的BFS（按入度为0节点的入队顺序遍历）只是拓扑排序的其中一种可能。以下是一个简单的示例图，其BFS遍历结果与另一种合法拓扑排序结果完全不同：

邻接表 #

• 节点A: [C, D]
• 节点B: [E]
• 节点C: []
• 节点D: []
• 节点E: []

结果对比 #

这个图中入度为0的节点是A和B：

1. BFS（Kahn算法）结果：假设初始队列先加入A再加入B，遍历顺序为 A → B → C → D → E
2. 另一种合法拓扑排序结果：B → A → E → C → D

后者完全符合拓扑排序的要求（所有边的起点均在终点之前），但与BFS遍历结果明显不同。

此外，如果执行不考虑入度的普通BFS（比如从节点C开始遍历），结果会是 C → D，这显然不是有效的拓扑排序——因为A、B这类前置节点未出现在序列中。

内容的提问来源于stack exchange，提问作者Mohak Gupta