反向边的拓扑排序是否与反转拓扑排序结果相同？
Is toposort of reverse edges same as reversing toposort result?
在所有边都处于错误方向的图上反转拓扑排序的结果是否会产生有效的拓扑顺序，就好像边在排序之前被反转一样？
a -> b
a -> c
b -> d
c -> d
可以给出 a b c d 的拓扑排序。反转此列表得到 d c b a。在拓扑排序之前反转图中的所有边也可以得到 d c b a。在一般情况下是这样吗？我猜不是，但我找不到失败的例子。
显然是，如果你从正确的角度看。
在topo-sort之后，如果我们将所有节点存储在一个列表中，则所有从任何边缘点向外的箭头都指向相同的方向。如果我们颠倒列表，所有箭头现在都指向相反的方向。由于所有箭头指向相同的方向，因此它是一种有效的拓扑排序。
而另一种方法，首先翻转所有边，然后执行拓扑排序显然会产生有效的拓扑排序，否则拓扑排序算法将被破坏。
这两种方法产生的确切总顺序可能不同，但它们都是有效的。
在所有边都处于错误方向的图上反转拓扑排序的结果是否会产生有效的拓扑顺序，就好像边在排序之前被反转一样？
a -> b
a -> c
b -> d
c -> d
可以给出 a b c d 的拓扑排序。反转此列表得到 d c b a。在拓扑排序之前反转图中的所有边也可以得到 d c b a。在一般情况下是这样吗？我猜不是，但我找不到失败的例子。
显然是，如果你从正确的角度看。
在topo-sort之后，如果我们将所有节点存储在一个列表中，则所有从任何边缘点向外的箭头都指向相同的方向。如果我们颠倒列表，所有箭头现在都指向相反的方向。由于所有箭头指向相同的方向，因此它是一种有效的拓扑排序。
而另一种方法，首先翻转所有边，然后执行拓扑排序显然会产生有效的拓扑排序，否则拓扑排序算法将被破坏。
这两种方法产生的确切总顺序可能不同，但它们都是有效的。