塔尔扬的强连通分量算法是否给出强连通分量的拓扑排序？

Question

我一直在研究SCC及其相关算法，发现人们几乎总是提到 Kosaraju 算法不仅可以找到 SCC，而且还能以（反向）拓扑排序的方式返回它们。

我的问题是：Tarjan 算法难道也不能以（反向）拓扑排序的方式返回结果吗？我从阅读的资料中发现它没有被提到（至少除了维基百科外）。

我一直在思考这个问题，觉得很有道理。当 tarjans_dfs 在某个节点 u 上调用时，所有从 u 可达的 SCC 都将在 u 的 SCC 之前找到。我错了吗？

维基百科说它实际上确实能够找到：

  

“虽然每个强连通分量内节点的顺序并没有什么特别之处，但该算法的一个有用性质是，在任何一个后继被发现之前，该算法都不会识别出任何强连通分量。因此，被识别的强连通分量的顺序构成了由这些强连通分量组成的 DAG 的逆拓扑排序。”

是我想多了，还是大家更知道 Kosaraju 算法可以找到拓扑序列，而不是 Tarjan 算法也可以呢？

- Augusto

---

我不明白你的问题是什么。你是在问这是真的吗？（是的）还是在问更多的人知道 Kosaraju 产生反向排序组件 vs Tarjan？我的意思是，除非有人做了一次调查，否则我们该如何回答这个问题？ - Asad Saeeduddin

哈哈，抱歉，我的主要问题是它是否真的是真的。谢谢。 - Augusto

属于cs.stackexchange.com。 - Anmol Singh Jaggi

Answer 1

是的，它可以。Tarjan的强连通分量算法通过对图进行深度优先搜索并在栈上跟踪SCC的根来工作。一种找到拓扑排序的方法是在图上执行DFS并跟踪退出顺序。这些节点在Tarjan的SCC算法中的退出顺序提供了拓扑排序。

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

“他为这个问题设计的数据结构以惊人的美妙方式组合在一起，以便您在探索有向图时需要查看的数量总是神奇地出现在您的指尖。而且他的算法还会作为副产品进行拓扑排序。”

- TheRobotCarlson

Answer 2

是的。由于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
}

- mvs

Answer 3

确实如此，我一直在使用它，也有同样的疑问。

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

- Fabio brunori