拓扑排序是否尝试对顶点或边进行排序？

Question

大家都快乐.

我目前正在学习拓扑排序,并对拓扑排序尝试排序的问题提出疑问.

该算法设计手册这样描述拓扑排序:

拓扑排序是有向无环图(DAG)上最重要的操作.它在一条线上对顶点进行排序,使得所有有向边从左向右.

这个大胆的部分让我困惑.拓扑排序排序顶点或所有有向边也是如此？

让我们举一个也在书中的例子.

因此对于上述DAG,我们可以得到拓扑排序(G,A,B,C,F,E,D).

我能理解这种.不仅顶点被排序,而且边缘也被排序,即G-> A-> B-> C-> F-> E-> D,这与上面的ADM书籍描述相符:all directed edges go from left to right

但是,如果我删除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拓扑排序,保证每个元素"不依赖"排序后出现的任何元素.

拓扑排序排序顶点或所有有向边也是如此？

拓扑排序对顶点进行排序,而不是边缘.它使用边作为排序顶点的约束.

但是,如果我删除B-> C的边缘怎么办？

是的,你添加的每个边缘,只需添加一个约束.请注意,拓扑排序可能有多个可行的解决方案[例如,对于没有边的图,任何排列都是可行的解决方案].删除约束,使任何先前的解决方案"解决更难的问题"仍然可行.

即使A是B和C的父级,我们仍然可以认为(G,A,B,C,F,E,D)是有效的排序吗？

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

希望能让它更加清晰.