使用 bfs 的拓扑顺序

Question

在 Sedgewick 和 Wayne 关于 java 算法的书中发现了以下问题：

4.2.19 拓扑排序和 BFS。解释为什么以下算法不一定会产生拓扑顺序：运行 BFS，并通过增加与各自源的距离来标记顶点。

我试图证明它找到一个反例。但是，每次我尝试时，都会得到一个拓扑顺序。我的意思是，我不明白为什么这不起作用：如果顶点的源在它之前，为什么我们没有拓扑顺序？

我想为了证明它，我们需要找到一个它的来源之前出现的顶点，但我不能。

有人有反例吗？提前致谢！

PS：这不是作业

@Edit：我尝试过像 1 <- 2 <- 0 <- 3 <- 4 这样的汉密尔顿路径，它给出 0 3 4 2 1，但是改变 0 3 和 4 的位置给了我一个拓扑顺序（但是，按照我获得的顺序，它不是）。我不确定这是否是拓扑顺序。

Answer 1

您不能使用 BFS，因为具有较高等级的节点可能具有较低等级的事件边。下面是一个例子：

假设您从源 (A) 启动 BFS。

使用您提出的算法，节点 D 将出现在节点 C 之前，这显然不是拓扑顺序。你真的必须使用 DFS。