9
$\begingroup$

In directed graph, to find strongly connected components why do we have to transpose adjacency matrix (reverses the direction of all edges) if we could use reversed list of nodes by they finishing time and then traverse original graph. In other words, we would find finish times of all vertices and start traversing from lowest finish time to greatest (by increasing finish time)?

Additionally, if we do topological sorting on some DAG, and then reverse edges (transpose adjacency matrix) and do topological sorting again - should we get to equal arrays, just in reversed order?

EDIT: Algorithm description from other topic: Correctness of Strongly Connected Components algorithm for a directed graph

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ 1. What research have you done? Have you read explanations of this algorithm in textbooks? It is explained in standard textbooks, and those explanations generally explain why it's necessary to reverse the graph. For instance, I like Dasgupta, Papadimitriou, and Vazirani's textbook and their explanation of the algorithm -- it explains the point you are asking about. 2. On your second question, what have you tried? Have you tried running it on a few examples? 3. One question per question, please. $\endgroup$
    – D.W. ♦
    Oct 22, 2014 at 15:53
  • $\begingroup$ @D.W. Well spotted! $\endgroup$
    – David Richerby
    Oct 22, 2014 at 16:44

2 Answers 2

Reset to default
7
$\begingroup$

Taking the transpose and using the list based on finishing time both together ensure that if you have edge A->B(in original graph) where A and B are simply connected sub-graphs than in second dfs A would have finished before start of B(See that in transposed graph edge is from B->A). If we do not take transpose then this is not ensured.

Example:

1->2

2->3

3->4

4->2

3->5

dfs(decreasing finishing time finishing times):1,2,3,5,4 Now if you start from 4 you will visit 5 through 4->2->3->5. But 4 and 5 are not simply connected.

For the second part you may or may not get reversed arrays depending on the order of supplying vertices.

Improve this answer
$\endgroup$
6
$\begingroup$

From the definition of strongly connected components : if every vertex is reachable from every other vertex.

The first DFS is to find all the vertices that are reachable from root vertex v. The second DFS is to check the reverse , i.e to find the subset(of all the above vertices) that can reach v.

Now this may sound a bit confusing, but the question 'whether any vertex u has a path to v', can be converted to an equivalent question on the transpose graph, 'whether v has a path to u'. Further detailing,'if a vertex u can reach v, then if you reverse the edges in the path between u and v, now equivalently v can reach u, and if there is no path from u to v in the original, then in the transpose there is no path between v and u'.

So instead of testing each vertex u ( which are reachable from v) and can reach v back, the second DFS on the transpose equivalently tests, if v can reach all u. The algorithm then returns a component, which has vertices that are both in the first DFS and the second one.

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.