Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Does Tarjan's SCC algorithm give a topological sort of the 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.

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

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:

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

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?

like image 444
Augusto Avatar asked Sep 23 '15 22:09

Augusto


People also ask

What does Tarjan's algorithm do?

Tarjan's strongly connected components algorithm is an algorithm in graph theory for finding the strongly connected components (SCCs) of a directed graph. It runs in linear time, matching the time bound for alternative methods including Kosaraju's algorithm and the path-based strong component algorithm.

Which algorithm is used for topological sorting?

Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge uv, vertex u comes before v in the ordering.

Can we use DFS for topological sort?

We can modify DFS to find the Topological Sorting of a graph. In DFS, We start from a vertex, we first print it, and then. Recursively call DFS for its adjacent vertices.

Is topological sort DFS or BFS?

Topological Sorting can be done by both DFS as well as BFS,this post however is concerned with the BFS approach of topological sorting popularly know as Khan's Algorithm.


1 Answers

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

like image 86
TheRobotCarlson Avatar answered Sep 28 '22 02:09

TheRobotCarlson