Kosaraju’s algorithm
Kosaraju's algorithm1 is an efficient method for finding the strongly connected components of a directed graph. The algorithm performs two depth-first searches: the first search constructs a list of nodes according to the structure of the graph, and the second search forms the strongly connected components.
Search 1
The first phase of Kosaraju's algorithm constructs a list of nodes in the order in which a depth-first search processes them. The algorithm goes through the nodes, and begins a depth-first search at each unprocessed node. Each node will be added to the list after it has been processed.
In the example graph, the nodes are processed in the following order:
The notation $x/y$ means that processing the node started at time $x$ and finished at time $y$. Thus, the corresponding list is as follows:
| node | processing time |
|---|---|
| 4 | 5 |
| 5 | 6 |
| 2 | 7 |
| 1 | 8 |
| 6 | 12 |
| 7 | 13 |
| 3 | 14 |
Search 2
The second phase of the algorithm forms the strongly connected components of the graph. First, the algorithm reverses every edge in the graph. This guarantees that during the second search, we will always find strongly connected components that do not have extra nodes.
After reversing the edges, the example graph is as follows:
After this, the algorithm goes through the list of nodes created by the first search, in reverse order. If a node does not belong to a component, the algorithm creates a new component and starts a depth-first search that adds all new nodes found during the search to the new component.
In the example graph, the first component begins at node 3:
Note that since all edges are reversed, the component does not leak to other parts in the graph.
The next nodes in the list are nodes 7 and 6, but they already belong to a component, so the next new component begins at node 1:
Finally, the algorithm processes nodes 5 and 4 that create the remaining strongly connected components:
The time complexity of the algorithm is $O(n+m)$, because the algorithm performs two depth-first searches.
1 According to [1], S. R. Kosaraju invented this algorithm in 1978 but did not publish it. In 1981, the same algorithm was rediscovered and published by M. Sharir [57].