Kosaraju's Algorithm: Find Strongly Connected Components

Description

Kosaraju's algorithm is a linear time algorithm to find the strongly connected components (SCCs) of a directed graph. A strongly connected component is a portion of a directed graph in which there is a path from each vertex to every other vertex. The algorithm uses depth-first search and works by performing two passes over the graph.

History

Kosaraju's algorithm was developed by S. Rao Kosaraju in 1978 but was first published by Micha Sharir in 1981. Kosaraju presented this algorithm during a classroom lecture at the University of Pennsylvania. The algorithm is notable for its simplicity and elegance, using two depth-first searches to find strongly connected components. Despite being discovered later than Tarjan's algorithm (1972), which solves the same problem, Kosaraju's algorithm is often preferred in teaching due to its simpler conceptual approach, even though both algorithms have the same linear time complexity.

How It Works

The algorithm works in three main steps:

First DFS Pass:
- Perform DFS on the original graph
- Store vertices in a stack as they finish (post-order)
Graph Transposition:
- Create a new graph by reversing all edges
- If edge (u,v) exists in original graph, add (v,u) in transposed graph
Second DFS Pass:
- Process vertices in order of the stack (most recently finished first)
- Each DFS tree in this pass is a strongly connected component

Visualization

Speed:

Click Start to begin

Implementation


from collections import defaultdict

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = defaultdict(list)
        
    def add_edge(self, u, v):
        self.graph[u].append(v)
        
    def transpose(self):
        g = Graph(self.V)
        
        for i in self.graph:
            for j in self.graph[i]:
                g.add_edge(j, i)
                
        return g
    
    def fill_order(self, v, visited, stack):
        visited[v] = True
        
        for i in self.graph[v]:
            if not visited[i]:
                self.fill_order(i, visited, stack)
                
        stack.append(v)
    
    def dfs(self, v, visited, scc):
        visited[v] = True
        scc.append(v)
        
        for i in self.graph[v]:
            if not visited[i]:
                self.dfs(i, visited, scc)
    
    def kosaraju(self):
        stack = []
        visited = [False] * self.V
        
        # Fill vertices in stack according to their finishing times
        for i in range(self.V):
            if not visited[i]:
                self.fill_order(i, visited, stack)
        
        # Create a reversed graph
        gr = self.transpose()
        
        # Mark all vertices as not visited for second DFS
        visited = [False] * self.V
        
        # Process all vertices in order defined by stack
        sccs = []
        while stack:
            i = stack.pop()
            if not visited[i]:
                scc = []
                gr.dfs(i, visited, scc)
                sccs.append(scc)
        
        return sccs

# Example usage
if __name__ == "__main__":
    g = Graph(5)
    g.add_edge(1, 0)
    g.add_edge(0, 2)
    g.add_edge(2, 1)
    g.add_edge(0, 3)
    g.add_edge(3, 4)
    
    print("Strongly Connected Components:")
    sccs = g.kosaraju()
    for i, scc in enumerate(sccs, 1):
        print(f"Component {i}: {scc}")


#include <iostream>
#include <vector>
#include <stack>
using namespace std;

class Graph {
    int V;
    vector<vector<int>> adj;
    
public:
    Graph(int vertices) : V(vertices) {
        adj.resize(V);
    }
    
    void addEdge(int u, int v) {
        adj[u].push_back(v);
    }
    
    Graph getTranspose() {
        Graph g(V);
        for(int v = 0; v < V; v++) {
            for(int u : adj[v]) {
                g.addEdge(u, v);
            }
        }
        return g;
    }
    
    void fillOrder(int v, vector<bool>& visited, stack<int>& Stack) {
        visited[v] = true;
        
        for(int i : adj[v]) {
            if(!visited[i]) {
                fillOrder(i, visited, Stack);
            }
        }
        
        Stack.push(v);
    }
    
    void DFSUtil(int v, vector<bool>& visited, vector<int>& scc) {
        visited[v] = true;
        scc.push_back(v);
        
        for(int i : adj[v]) {
            if(!visited[i]) {
                DFSUtil(i, visited, scc);
            }
        }
    }
    
    vector<vector<int>> kosaraju() {
        stack<int> Stack;
        vector<bool> visited(V, false);
        
        // Fill vertices in stack according to their finishing times
        for(int i = 0; i < V; i++) {
            if(!visited[i]) {
                fillOrder(i, visited, Stack);
            }
        }
        
        // Create a reversed graph
        Graph gr = getTranspose();
        
        // Mark all vertices as not visited for second DFS
        fill(visited.begin(), visited.end(), false);
        
        // Process all vertices in order defined by stack
        vector<vector<int>> sccs;
        while(!Stack.empty()) {
            int v = Stack.top();
            Stack.pop();
            
            if(!visited[v]) {
                vector<int> scc;
                gr.DFSUtil(v, visited, scc);
                sccs.push_back(scc);
            }
        }
        
        return sccs;
    }
};

int main() {
    Graph g(5);
    g.addEdge(1, 0);
    g.addEdge(0, 2);
    g.addEdge(2, 1);
    g.addEdge(0, 3);
    g.addEdge(3, 4);
    
    cout << "Strongly Connected Components:\n";
    auto sccs = g.kosaraju();
    for(int i = 0; i < sccs.size(); i++) {
        cout << "Component " << i+1 << ": ";
        for(int v : sccs[i]) {
            cout << v << " ";
        }
        cout << endl;
    }
    
    return 0;
}


public class Graph
{
    private int V;
    private List<List<int>> adj;
    
    public Graph(int vertices)
    {
        V = vertices;
        adj = new List<List<int>>();
        for (int i = 0; i < V; i++)
        {
            adj.Add(new List<int>());
        }
    }
    
    public void AddEdge(int u, int v)
    {
        adj[u].Add(v);
    }
    
    private Graph GetTranspose()
    {
        Graph g = new Graph(V);
        for (int v = 0; v < V; v++)
        {
            foreach (int u in adj[v])
            {
                g.AddEdge(u, v);
            }
        }
        return g;
    }
    
    private void FillOrder(int v, bool[] visited, Stack<int> stack)
    {
        visited[v] = true;
        
        foreach (int i in adj[v])
        {
            if (!visited[i])
            {
                FillOrder(i, visited, stack);
            }
        }
        
        stack.Push(v);
    }
    
    private void DFSUtil(int v, bool[] visited, List<int> scc)
    {
        visited[v] = true;
        scc.Add(v);
        
        foreach (int i in adj[v])
        {
            if (!visited[i])
            {
                DFSUtil(i, visited, scc);
            }
        }
    }
    
    public List<List<int>> Kosaraju()
    {
        Stack<int> stack = new Stack<int>();
        bool[] visited = new bool[V];
        
        // Fill vertices in stack according to their finishing times
        for (int i = 0; i < V; i++)
        {
            if (!visited[i])
            {
                FillOrder(i, visited, stack);
            }
        }
        
        // Create a reversed graph
        Graph gr = GetTranspose();
        
        // Mark all vertices as not visited for second DFS
        Array.Fill(visited, false);
        
        // Process all vertices in order defined by stack
        List<List<int>> sccs = new List<List<int>>();
        while (stack.Count > 0)
        {
            int v = stack.Pop();
            
            if (!visited[v])
            {
                List<int> scc = new List<int>();
                gr.DFSUtil(v, visited, scc);
                sccs.Add(scc);
            }
        }
        
        return sccs;
    }
}

public class Program
{
    public static void Main()
    {
        Graph g = new Graph(5);
        g.AddEdge(1, 0);
        g.AddEdge(0, 2);
        g.AddEdge(2, 1);
        g.AddEdge(0, 3);
        g.AddEdge(3, 4);
        
        Console.WriteLine("Strongly Connected Components:");
        var sccs = g.Kosaraju();
        for (int i = 0; i < sccs.Count; i++)
        {
            Console.Write($"Component {i + 1}: ");
            Console.WriteLine(string.Join(" ", sccs[i]));
        }
    }
}

Complexity Analysis

Time Complexity

The time complexity of Kosaraju's algorithm is O(V + E), where V is the number of vertices and E is the number of edges in the graph. This can be broken down into:

First DFS: O(V + E)
- Visits each vertex once: O(V)
- Traverses each edge once: O(E)
Graph Transposition: O(V + E)
- Creating new adjacency list: O(V)
- Copying and reversing edges: O(E)
Second DFS: O(V + E)
- Visits each vertex once: O(V)
- Traverses each edge once: O(E)

Total: O(V + E) + O(V + E) + O(V + E) = O(V + E)

Space Complexity

The space complexity is O(V), which includes:

Visited Array: O(V)
- Boolean array to track visited vertices
Stack: O(V)
- Stores vertices in order of finish time
Transposed Graph: O(V + E)
- New adjacency list structure
- Reversed edges
Output Storage: O(V)
- Storage for strongly connected components

While the transposed graph requires O(V + E) space, the original space complexity is typically cited as O(V) since we assume the input graph already uses O(V + E) space.

Quick Info

Kosaraju's Algorithm