graph - 原始图的拓扑排序是否与转置图的 dfs 相同

Question

我有一种直觉，原始图的拓扑排序与转置图的 dfs 相同（反转所有边）

 A -> B -> C
 D -> B

拓扑排序是 [D, A, B, C] 或 [A, D, B, C]

如果我转置图形（反转所有边）

  C -> B -> A   
       B -> D

dfs 还给出 [D, A, B, C] 或 [A, D, B, C]

拜托，我无法在数学上证明/反驳它。如果命题不正确，反例会有所帮助

标签： graphtopological-sort

Answer 1

这不是巧合——您刚刚重新发现了一种用于查找拓扑排序的通用算法！

一种通常用于查找拓扑排序的算法通过执行 DFS 并以完成时间的相反顺序写出节点来工作。（试试看！）您的算法本质上与此等效。

其他算法——比如 Kosaraju 用于计算强连通分量的算法——利用了类似的见解。