Kosaraju’s algorithm uses the DFS stack to determine the topological sorting of the strongly connected components of a directed graph. Complexity: \(O(|V|+|E|)\) (Two DFS; Creating components as hashmaps and doing lookups take \(O(|V|)\))
Since we are looking at components as nodes in the topological sorting, we focus on the DFS visiting/leaving time regarding a whole component. The visiting time \(t^{visit}\) for a component is the time when the first node in the component get visited, similarly the leaving time \(t^{leave}\) is for the last component node popped out of the DFS stack.
Kosaraju’s utilizes the leaving times of the components to decide the topological sorting sequence.
That is, if a component \(C_i\) is later in the sequence than \(C_j\), then we have for the leaving time \(t^{leave}_i < t^{leave}_j\). The rationale is: After DFS leaves from the last node of \(C_i\), it will need to utilize a path through \(C_j\) to report back to the starting root.
The algorithm goes:
1
2
3
4
5
6
7
0. Directed graph G. Maintain a list L to receive the nodes popping out from the DFS stack.
1. Repeatedly perform DFS from a random node in the remaining unvisited nodes in G. When finishing the exploration of a node (popping from the DFS stack), put it in the list L.
2. Revert the list L to start from the last popped node.
3. Revert the graph edges of G.
4. Take the first node from L, perform DFS to get the first component (source).
5. Check the next node until a node not in the first component, repeat 4 to get the second component.
6. Repeat 4-5 until L is exhausted.
The result is only a collection of the components. The directional edges (relationships) between the components are unknown.
Reconstruct the directional edges between SCC
| To reconstruct these directional edges, for each edge \((u, v)\), knowing that the node \(u\) in component \(C_i\), if the node \(v\) in component \(C_j\) with \(i \neq j\), add a link in the meta-graph for $(i, j)$. This will take $$O( | E | )$$. |