Tarjan 的 SCC 算法是否给出 SCC 的拓扑排序？

Question

我一直在研究 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 的算法更广为人知？

Answer 1

确实如此，我一直在使用它，我想到了同样的问题。

我实际上没有时间来演示它，但每个测试用例（成千上万）总是 returns 一个拓扑排序的压缩图。

Answer 2

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

Donald Knuth 在谈到 Tarjan 的 SCC 算法时甚至提到了它 in an interview，他说这是他最喜欢的算法之一：

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.

Answer 3

是的。由于 Tarjan 基于深度优先搜索，您所要做的就是在每个顶点达到 "closed" 状态时将顶点添加到列表的顶部。（即它对该顶点的 dfs/tarjan 调用结束)

这是一个C/C++/伪代码示例：

void tarjan(int u) {
    visited[u] = true;
    closed[u] = false;
    //dfs + tarjan processing
    for (vi v = G[u].begin(); v != G[u].end(); v++) {
        if (!visited[*v]) {
            dfs(*v);
        } else if (!closed[*v]) {
            // has Cycle
        }
    }
    closed[u] = true;
    //add u to the top of your list here
}

Tarjan 的 SCC 算法是否给出 SCC 的拓扑排序？

Does Tarjan's SCC algorithm give a topological sort of the SCC?

algorithm

graph

topological-sort

tarjans-algorithm