algorithm - 使用 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。