algorithm - 拓扑排序是要对顶点还是边进行排序？

Question

大家复活节快乐。

我目前正在学习拓扑排序，并且对什么拓扑排序试图真正排序有疑问。

Algorithm Design Manual以这种方式描述拓扑排序:

Topological sorting is the most important operation on directed acyclic graphs (DAGs). It orders the vertices on a line such that all directed edges go from left to right.

这个粗体部分让我感到困惑。那么拓扑排序是排序顶点还是所有有向边呢？

举个例子，书上也有。

所以对于上面的DAG，我们可以得到一个拓扑排序(G,A,B,C,F,E,D)。

我能理解这种。不仅顶点被排序，边也被排序，即 G->A->B->C->F->E->D，这符合上面 ADM 书上的描述:all directed edges从左到右

但是如果我去掉 B->C 的边呢？ 结果图仍然是一个 DAG，但是拓扑排序仍然是 (G, A, B, C, F, E , D)?

如果是，那么我认为边没有排序，因为 A->B->C 不再存在，而是 A->B 和 A->C。那么，这种情况仍然是有效的拓扑排序吗？我们还能认为即使 A 是 B 和 C 的父级，(G, A, B, C, F, E, D) 也是有效的排序？

谢谢

Answer 1

您可以将其视为元素的排序。

设 v1,v2,...,vn 为元素。并让边缘(vi,vj)表示vi<vj .拓扑排序保证排序后:对于每个 vi ，并且对于每个 vj这样 i < j , vj不大于 vi

或者用其他表示法:假设 (vi,vj)表示vj依赖于 vi ，拓扑排序保证每个元素“不依赖于”在排序中出现在它之后的任何元素。

So does the topological sorting sort vertices or all directed edges?

拓扑排序排序的是顶点，而不是边。它使用边作为对顶点排序的约束。

But what if I remove the edge of B->C?

是的，你添加的每条边，只是添加一个约束。请注意，拓扑排序可能有不止一个可行的解决方案[例如，对于没有边的图，任何排列都是可行的解决方案]。移除约束，使得任何先前的“解决更难问题”的解决方案仍然可行。

Can we still think (G, A, B, C, F, E, D) is a valid sort even if A is the parent of B and C?

没有问题!在拓扑排序中A出现在B、C之前，所以是他们的父亲没有问题。

希望这能让它更清楚一些。