通过圆弧进行拓扑排序

Question

确实只需要一些指导： 通过圆弧定义的拓扑排序（从我的问题） - 是对方向图中的所有圆弧进行排序的一种方式，因此插入到顶点的所有圆弧必须先于从这个顶点出来。

Answer 1

无需在拓扑排序中改变任何东西，你可以使用它和后期处理。

高电平伪代码：

1. 运行拓扑排序，让所得到的数组是arr
2. 创建空边缘列表中，让它成为l
在 arr [有序迭代]
3. 为每个顶点v ：
   3.1。对于每个(v,u) in E：
   3.1.1。追加(v,u) to l
4. 回报l

这种方法的好处是，你可以使用拓扑排序为黑盒，而无需修改它，只是后期处理，以获得所需的结果。

正确性 [证明的草图]：
由于每个边缘(v,u) - u显示在拓扑排序v后，在打印它，它是通过v完成，并且因此(v,u)打印任何顶点之前被印刷附于u。

复杂：
O(|V|+|E|)拓扑排序，O(|V|+|E|)用于后处理[迭代的所有顶点和所有边缘。

Answer 2

“传统”拓扑排序是对顶点进行排序，而这是对弧进行排序。否则，原理是一样的...