12

我一直在研究 SCC 和有关它们的算法，并且我看到人们几乎总是提到 Kosaraju 的算法找到 SCC 并以（反向）拓扑排序对其进行排序。

我的问题是：Tarjan 的算法不是也找到了（反向）拓扑排序吗？我发现它没有被提及（至少从我读过的地方，维基百科除外）。

我一直在考虑它并且完全有道理。当在某个节点 u 上调用 tarjans_dfs 时，所有可以从 u 到达的 SCC 都将在 u 的 SCC 之前找到。我错了吗？

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

“虽然每个强连接组件中节点的顺序没有什么特别之处，但该算法的一个有用特性是，在其任何继任者之前不会识别强连接组件。因此，强连接组件的顺序是识别构成了由强连接组件形成的 DAG 的反向拓扑排序。”

是我的想法，还是说 Kosaraju 的算法找到拓扑顺序比 Tarjan 的算法也能找到拓扑顺序更广为人知？

4

3 回答 3

4

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

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

他为这个问题设计的数据结构以一种非常漂亮的方式组合在一起，因此您在探索有向图时需要查看的数量总是神奇地触手可及。而且他的算法也将拓扑排序作为副产品。

于 2017-03-09T17:14:33.350 回答
0

是的。由于 Tarjan 基于深度优先搜索，您所要做的就是在每个顶点达到“关闭”状态时将顶点添加到列表的顶部。（即，它的 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
}
于 2017-04-24T22:36:48.680 回答
-1

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

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

于 2016-06-01T17:39:55.060 回答