Tarjan的SCC算法是否给出了SCC的拓扑类型？

Question

我一直在研究关于它们的SCC和算法,我已经看到人们几乎总是提到Kosaraju的算法找到SCC并且还以(反向)拓扑排序对它们进行排序.

我的问题是:Tarjan的算法是否也找到(反向)拓扑排序？我发现它没有被提及(至少从我读过的地方,除了维基百科).

我一直在考虑它,并且非常有意义.当在某个节点u上调用tarjans_dfs时,可以在u的SCC之前找到所有可从u访问的SCC.我错了吗？

维基百科说它确实找到了它:

"虽然每个强连接组件中的节点顺序没有什么特别之处,但算法的一个有用属性是在任何后继组件之前不会识别出强连接组件.因此,强连接组件的顺序是确定的是由强连通分量形成的DAG的反向拓扑类型."

这是我的想法,还是更为人所知的是,Kosaraju的算法找到拓扑顺序而不是Tarjan也这样做的事实？

Answer 1

是的，它确实。Tarjan 的 SCC 算法的工作原理是在图上执行 DFS 并跟踪堆栈上 SCC 的根。查找拓扑排序的一种方法是对图执行 DFS 并跟踪退出顺序。Tarjan 的 SCC 算法中这些节点的退出顺序提供了拓扑排序。

Donald Knuth 甚至在一次采访中谈到 Tarjan 的 SCC 算法时提到了这一点，他说这是他最喜欢的算法之一：

他为这个问题设计的数据结构以一种令人惊叹的美丽方式组合在一起，因此您在探索有向图时需要查看的数量总是神奇地触手可及。他的算法还作为副产品进行拓扑排序。