大家都快乐 .
我目前正在学习拓扑排序，并对拓扑排序尝试排序的问题提出疑问 .
Algorithm Design Manual以这种方式描述拓扑排序：
拓扑排序是有向无环图（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
But what if I remove the edge of 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）是有效的排序吗？
谢谢
1 回答
您可以将其视为元素的排序 .
让v1，v2，...，vn成为元素 . 并让边缘
(vi,vj)表示vi<vj. 拓扑排序保证在排序后：对于每个vi，对于每个vj，使i < j，vj不大于vi或者在其他表示法中：假设
(vi,vj)表示vj依赖于vi，拓扑排序保证每个元素"does not depend"在排序后出现在其后面的任何元素上 .拓扑排序对顶点进行排序，而不是边缘 . 它使用边作为排序顶点的约束 .
是的，你添加的每个边缘，只需添加一个约束 . 请注意，拓扑排序可能有多个可行的解决方案[例如，对于没有边的图，任何排列都是可行的解决方案] . 删除约束，使任何先前的解决方案“解决更难的问题”仍然可行 .
没问题！ A在拓扑排序中出现在B，C之前，所以没有问题是他们的父亲 .
希望能让它更加清晰 .