我一直在研究 SCC 和有关它们的算法，我看到人们几乎总是提到 Kosaraju 的算法找到了 SCC，并且还以(反向)拓扑排序对它们进行排序。
我的问题是:Tarjan 的算法是否也找到了(反向)拓扑排序？我发现它没有被提及(至少从我读过的地方，维基百科除外)。
我一直在思考这个问题，并且非常有道理。当在某个节点 u 上调用 tarjans_dfs 时，将在 u 的 SCC 之前找到从 u 可达的所有 SCC。我错了吗？
维基百科说它确实找到了它:
"While there is nothing special about the order of the nodes within each strongly connected component, one useful property of the algorithm is that no strongly connected component will be identified before any of its successors. Therefore, the order in which the strongly connected components are identified constitutes a reverse topological sort of the DAG formed by the strongly connected components."
这是我的想法，还是 Kosaraju 的算法找到拓扑顺序比 Tarjan 的算法更广为人知？
最佳答案
是的，确实如此。 Tarjan 的 SCC 算法通过在图上执行 DFS 并在堆栈上跟踪 SCC 的根来工作。查找拓扑排序的一种方法是在图上执行 DFS 并跟踪退出顺序。 Tarjan 的 SCC 算法中这些节点的退出顺序提供了一种拓扑排序。
Donald Knuth 甚至提到了它 in an interview在谈到 Tarjan 的 SCC 算法时，他说这是他最喜欢的算法之一:
The data structures that he devised for this problem fit together in an amazingly beautiful way, so that the quantities you need to look at while exploring a directed graph are always magically at your fingertips. And his algorithm also does topological sorting as a byproduct.
关于algorithm - Tarjan 的 SCC 算法是否给出 SCC 的拓扑排序？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/32750511/