使用bfs的拓扑顺序 [英] Topological order using bfs

问题描述

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

The following question was found in Sedgewick and Wayne book about algorithms in java:

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

4.2.19 Topological sort and BFS. Explain why the following algorithm does not necessarily produce a topological order: Run BFS, and label the vertices by increasing distance to their respective source.

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

I was trying to prove it finding a counter example. But, everytime I try, I get a topological order. I mean, I don't understand why this not work: If the source of a vertex comes before it, why don't we have a topological order?

我想证明这一点，我们需要找到它的来源之前存在的顶点，但我不能。

I think to prove it, we need to find a vertex that its source comes before, but I couldn't.

有人反对吗？

PS：这不是作业

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

@ I've tried an hamiltonian path like 1 <- 2 <- 0 <- 3 <- 4, which gives 0 3 4 2 1, but changing the positions of 0 3 and 4 gives me a topological order (but, in the order that I obtained, it is not). I am not sure this is or not a topological order, then.

推荐答案

您不能使用BFS，因为具有更高节点的节点等级可能具有较低等级的入射边。举个例子：

You cannot use BFS, because a node with a higher rank may have an incident edge with a lower rank. Here's an example:

假设您从源（A）启动BFS。

Let's say you start BFS at the source (A).

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

With the algorithm you proposed, node D would come before node C, which is clearly not a topological order. You really have to use DFS.

这篇关于使用bfs的拓扑顺序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！