Kosaraju's Algorithm in Java: Two-Pass SCC Detection

While Tarjan's algorithm is known for its single-pass efficiency, Kosaraju's Algorithm is often preferred for its conceptual simplicity. It leverages a fundamental property of directed graphs: a graph and its transpose share the same Strongly Connected Components (SCCs).

The Core Concept: Two DFS Passes

Kosaraju's algorithm finds SCCs in three main steps:

1. First DFS Pass: Perform a DFS on the original graph and push nodes onto a stack based on their finishing times (similar to topological sort).
2. Graph Transposition: Create a new graph by reversing the direction of every edge in the original graph.
3. Second DFS Pass: Pop nodes from the stack and perform a DFS on the transposed graph. Each DFS call from a popped node identifies one complete SCC.

Kosaraju's Algorithm Implementation in Java

import java.util.*;

public class KosarajuSCC {
    private int n;
    private List<List<Integer>> adj;
    private List<List<Integer>> transposedAdj;
    private boolean[] visited;
    private Stack<Integer> stack;

    public List<List<Integer>> findSCCs(int n, List<List<Integer>> adj) {
        this.n = n;
        this.adj = adj;
        this.visited = new boolean[n];
        this.stack = new Stack<>();
        List<List<Integer>> sccs = new ArrayList<>();

        // Step 1: First DFS Pass to fill the stack
        for (int i = 0; i < n; i++) {
            if (!visited[i]) fillStack(i);
        }

        // Step 2: Transpose the graph
        transpose();

        // Step 3: Second DFS Pass on the transposed graph
        Arrays.fill(visited, false);
        while (!stack.isEmpty()) {
            int node = stack.pop();
            if (!visited[node]) {
                List<Integer> scc = new ArrayList<>();
                dfsTransposed(node, scc);
                sccs.add(scc);
            }
        }
        return sccs;
    }

    private void fillStack(int u) {
        visited[u] = true;
        for (int v : adj.get(u)) {
            if (!visited[v]) fillStack(v);
        }
        stack.push(u);
    }

    private void transpose() {
        transposedAdj = new ArrayList<>();
        for (int i = 0; i < n; i++) transposedAdj.add(new ArrayList<>());
        for (int u = 0; u < n; u++) {
            for (int v : adj.get(u)) {
                transposedAdj.get(v).add(u);
            }
        }
    }

    private void dfsTransposed(int u, List<Integer> scc) {
        visited[u] = true;
        scc.add(u);
        for (int v : transposedAdj.get(u)) {
            if (!visited[v]) dfsTransposed(v, scc);
        }
    }
}

Why use Kosaraju's?

Real-World Applications

1. Social Network Analysis: Finding groups of people who all follow each other.
2. Compiler Optimization: Identifying loops in a control-flow graph.
3. Data Mining: Discovering clusters of related information in a directed dataset.

Summary

Kosaraju's algorithm is a beautiful demonstration of how reversing a graph can reveal its hidden structure. By combining two simple DFS passes with a stack, it provides a robust and easy-to-implement solution for SCC detection. Understanding both Kosaraju's and Tarjan's algorithms shows that you can evaluate multiple approaches to the same problem based on complexity and maintainability.