What is Kosaraju’s Algorithm?

Kosaraju’s Algorithm is a classic graph theory algorithm used to find the Strongly Connected Components (SCCs) in a directed graph. A strongly connected component is a maximal subgraph where every vertex is reachable from every other vertex. Kosaraju’s algorithm is efficient, with a time complexity of O(V+E), where V is the number of vertices and E is the number of edges.

Kosaraju’s algorithm consists of two main passes over the graph:

1. First Pass: Perform a Depth-First Search (DFS) on the original graph to compute the finishing times of the vertices.
2. Second Pass: Perform a DFS on the transposed graph (graph with all edges reversed) in the order of decreasing finishing times obtained in the first pass.

The algorithm can be broken down into the following steps:

Steps of Kosaraju’s Algorithm:

1. Initialize: Create an empty stack to store the order of finishing times and a visited list to track visited vertices.
2. First DFS: Perform DFS on the original graph. Push each vertex onto the stack once its DFS finishes.
3. Transpose Graph: Reverse the direction of all edges in the graph to get the transposed graph.
4. Second DFS: Perform DFS on the transposed graph using the vertices in the order defined by the stack (from the first DFS).
5. Collect SCCs: Each DFS in this second pass gives one SCC.