topological-sort - 反向边的拓扑排序是否与反转拓扑排序结果相同？

Question

在所有边都处于错误方向的图上反转拓扑排序的结果是否会产生有效的拓扑顺序，就好像边在排序之前被反转一样？

a -> b
a -> c
b -> d
c -> d

可以给出 a b c d 的拓扑排序。反转这个列表得到 d c b a。在拓扑排序之前反转图中的所有边也可以得到 d c b a。在一般情况下是这样吗？我猜不是，但我找不到失败的例子。

Answer 1

从正确的角度来看，显然是这样。

在拓扑排序之后，如果我们将所有节点存储在一个列表中，则所有从任何边缘点向外的箭头都指向相同的方向。如果我们颠倒列表，所有箭头现在都指向相反的方向。由于所有箭头指向相同的方向，因此它是一种有效的拓扑排序。

另一种方法，首先翻转所有边然后执行拓扑排序显然会产生有效的拓扑排序，或者拓扑排序算法被破坏。

这两种方法产生的确切总顺序可能不同，但它们都是有效的。