Tarjan的SCC算法是否提供SCC的拓扑类型？ [英] Does Tarjan's SCC algorithm give a topological sort of the SCC?

问题描述

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

I've been studying SCC and algorithms about them, and I've seen that people almost always mention that Kosaraju's algorithm finds the SCC and also gives them ordered in a (reversed) topological sort.

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

My question is: doesn't Tarjan's algorithm also find a (reversed) topological sort? I've found that it isn't mentioned (at least from where I've read, except wikipedia).

我一直在考虑它，并说得很对。 。在u的某些节点上调用tarjans_dfs时，将在u的SCC之前找到从u可访问的所有SCC。我错了吗？

I've been thinking about it and make perfect sense. When tarjans_dfs is called on some node u, all SCCs that are reachable from u will be found before u's SCC. Am I wrong?

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

Wikipedia says it actually does find it:

尽管
中每个强连接组件内的节点顺序没有什么特别之处，但是
算法的一个有用特性是，在任何后继组件之前都不会标识
强连接组件。因此，确定
强连接的组件的顺序构成了由强连接
组件形成的DAG的反向
拓扑类型。

"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."

这是我的主意，还是比起Tarjan的算法更了解Kosaraju的算法找到拓扑顺序？

Is it my idea, or is it much more known that Kosaraju's algorithm finds the topological order than the fact that Tarjan's also does it?

推荐答案

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

Yes, it does. Tarjan's SCC algorithm works by performing a DFS on a graph and keeping track of the roots of the SCCs on a stack. One method of finding a topological sort is performing a DFS on a graph and keeping track of the exit order. The exit order of these nodes in Tarjan's SCC algorithm provide a topological sort.

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

Donald Knuth even mentions it in an interview when talking about Tarjan's SCC algorithm, which he says is one of his favorite:

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

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.

这篇关于Tarjan的SCC算法是否提供SCC的拓扑类型？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！