Kosaraju's Algorithm

Kosaraju's Algorithm is a linear-time algorithm used to find all Strongly Connected Components (SCCs) in a directed graph. A sub-graph is strongly connected if there is a path in both directions between every pair of vertices in that sub-graph.

         Real-World Application:
        Kosaraju's algorithm is extensively used in social network analysis (finding closed groups
        where members mutually follow or interact with each other), optimizing compiler
        computations, and identifying highly interdependent web pages in search engine algorithms.
      

The 3-Step Principle

The magic of Kosaraju's algorithm lies in reversing the directions of all edges in the graph:

Step 1 (Ordering): Perform a standard DFS on the original graph. Once a node has no more unvisited neighbors, push it onto a stack. This records nodes in order of their finishing times.
Step 2 (Transpose Graph): Reverse every edge in the graph ($u \rightarrow v$ becomes $v \rightarrow u$).
Step 3 (Extraction): Pop nodes from the stack one by one. If a node hasn't been visited in the transposed graph, launch a new DFS starting from it. All reachable nodes belong to the same Strongly Connected Component.

Algorithm Walkthrough

def kosaraju():
    all_nodes = get_all_nodes()
    visited = set()
    stack = []
    
    # Pass 1: Standard DFS to fill the stack by finish time
    def dfs_first_pass(u):
        visited.add(u)
        for v in neighbors(u):
            if v not in visited:
                dfs_first_pass(v)
        stack.append(u)
        
    for node in all_nodes:
        if node not in visited:
            dfs_first_pass(node)
            
    # Pass 2: Reverse graph representation
    reversed_graph = transpose_edges(all_nodes)
            
    # Pass 3: Process stack on the transposed graph
    visited.clear()
    scc_count = 0
    
    while len(stack) > 0:
        root = stack.pop()
        if root not in visited:
            scc_count += 1
            dfs_second_pass(root, scc_count)

kosaraju()

Complexity

Metric	Complexity	Explanation
Time Complexity	$O(V + E)$	Where $V$ is the number of vertices and $E$ is the number of edges. We perform two complete DFS traversals and one graph transposition step, all of which run in linear time.
Space Complexity	$O(V + E)$	Space is required for storing the stack ($O(V)$), the recursion tree, and the reversed adjacency list ($O(V + E)$).