algorithm - 按弧的拓扑排序

Question

真的只需要一些指导: 按弧定义的拓扑排序(来 self 的问题)- 是一种对有向图中所有弧进行排序的方法，因此所有插入顶点的弧都必须在从该顶点出来的弧之前出现。

Answer 1

无需更改拓扑排序中的任何内容，您可以直接使用它并进行后处理。

高级伪代码:

1. 运行拓扑排序，让结果数组为arr
2. 创建空边列表，让它成为l
3. 对于 arr 中的每个顶点 v [有序迭代]:
   3.1。对于 E 中的每个 (v,u):
   3.1.1．将 (v,u) 附加到 l
4. 返回 l

此方法的优点是您可以将拓扑排序用作黑盒，无需修改，只需进行后处理即可获得所需结果。

正确性 [证明草图]:
因为对于每条边 (v,u) - u 在拓扑排序中出现在 v 之后，当你打印它时，它是通过 v 完成，因此 (v,u) 在打印附加到 u 的任何顶点之前打印。

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