Why do we need to run DFS on the complement of a graph in the Kosaraju's algorithm?

Question

There's a famous algorithm to find the strongly connected components called Kosaraju's algorithm, which uses two DFS's to solve this problem, and runs in θ(|V| + |E|) time.

First we use DFS on complement of the graph (G^R) to compute reverse postorder of vertices, and then we apply second DFS on the main graph G by taking vertices in reverse post order to compute the strongly connected components.

Although I understand the mechanics of the algorithm, I'm not getting the intuition behind the need of the reverse post order.

How does it helps the second DFS to find the strongly connected components?

Answer 1

suppose result of the first DFS is:

----------v1--------------v2-----------

where "-" indicates any number and all the vertices in a strongly connected component g appear between v1 and v2.

DFS by post order gives the following guarantee that

• all vertices after v2 would not points to g in the reverse graph(that is to say, you cannot reach these vertices from g in the origin graph)
• all vertices before v1 cannot be pointed to from g in the reverse graph(that is to say, you cannot reach g from these vertices in the origin graph)

in one word, the first DFS ensures that in the second DFS, strongly connected components that are visited earlier cannot have any edge points to other unvisited strongly connected components.

Some Detailed Explanation

let's simplify the graph as follow:

• the whole graph is G
• G contains two strongly connected components, one is g, the other one is a single vertex v
• there is only one edge between v and g, either from v to g or from g to v, the name of this edge is e
• g', e' represent the reverse of g, e

the situation in which this algorithm could fail can be conclude as

1. start DFS from v, and e' points from v to g'
2. start DFS from a vertex inside of g', and e' points from g' to v

For situation 1

origin graph would be like g-->v, and the reversed graph looks like g'<--v.

To start the second DFS from v, the post order generated by first DFS need to be something like

g1, g2, g3, ..., v

but you would easily find out that neither starting the first DFS from v nor from g' can give you such a post order, so in this situation, it is guaranteed be the first DFS that the second DFS would not start from a vertex that both be out of and points to a strongly connected component.

For situation 2

similar to the situation 1, in situation 2, where the origin graph is g<--v and the reversed on is g'-->v, it is guaranteed that v would be visited before any vertex in g'.

Answer 2

1. When you run DFS on a graph for the first time, for every node you visit you get the knowledge about all nodes that are reachable from that node (you get this information after the first DFS is finished).

2. Then, when you inverse all the vertices and run the DFS once more, for every node you visit you get the knowledge about all nodes that can reach that node in the non-inverted graph (again, you get this info after the second DFS finished).

Example: let's say your first DFS reaches node X. From that node "you can see" all the neighbours you can visit. (I hope this is pretty understandable). Then, let's say your second DFS reaches that node X, but this time all the vertices are inverted. If then from your node X "you can see" any other nodes, it means that before inverting the vertices the node X was reachable from all the neighbours you see now. By calling the second DFS in the correct order you get for every node X all the nodes that where reachable from X in both DFS trees (and so, for every node X you get the nodes that were both reachable from X and could reach X - those are strongly connected components by definition).

Answer 3

Suppose the list L is the post-order DFS visit of nodes. u->v indicates that there exists a forwarding path from u to v.

If u->v and not v->u, then u must appear at the left of v in L. The nodes in a SCC, such as v and w, however, may appear in any arbitrary order on the list L.

So, if a node x appear strictly before y on the list L:

• case1: x->y and y->x, like the case of v and w
• case2: x->y and not y->x, like the case of u and v
• case3: not x->y and not y->x

The Kosaraju's algorithm iterates through L from left to right and run DFS starting from each node on the transpose graph (where the direction of edges are reversed). If some node is reachable by DFS and it does not belong to any SCC, then we add this node to the SCC of current root.

In case 1, we will add y to the SCC of x. In case 3, y and x are in different SCCs.

Case 2 requires some special attention. At the time we call DFS from y, x is already in some other SCC, so we will not add x to the SCC of y. Imagine if you called the DFS starting from root y before the DFS starting from root x, then x would be added to the SCC of y, which is wrong.

In short, the first DFS arranges those nodes which can reach y but can not be reached from y on its left. So the second DFS is able to avoid adding such nodes x to the SCC of y.