Strongly Connected Components Using Kosaraju's Algorithm

Problem Statement❯

Given a directed graph with V vertices (numbered from 0 to V - 1) and E directed edges, your task is to find the number of Strongly Connected Components (SCCs).

A strongly connected component is a maximal group of vertices such that every vertex is reachable from every other vertex in the group via directed paths.

Examples❯

Graph (Adjacency List)	Vertices	Edges	Output	Description
{ 0: [1], 1: [2], 2: [0], 3: [4] }	5	[(0→1), (1→2), (2→0), (3→4)]	2	Two SCCs: {0,1,2} and {3,4}
{ 0: [1], 1: [2], 2: [3], 3: [] }	4	[(0→1), (1→2), (2→3)]	4	No cycles, each node is its own SCC
{}	0	[]	0	Empty graph has no components
{ 0: [0] }	1	[(0→0)]	1	Self loop is a valid SCC
{ 0: [1], 1: [2], 2: [0], 3: [2,4], 4: [3] }	5	[(0→1), (1→2), (2→0), (3→2), (3→4), (4→3)]	2	{0,1,2} and {3,4} are two SCCs

Solution❯

Understanding the Problem

In a directed graph, a Strongly Connected Component (SCC) is a group of vertices where every vertex is reachable from every other vertex in that group. In simpler terms, if you can start at any node in the group and reach all the others through the directed edges—and also get back to the starting node—then those nodes form an SCC.

Our goal is to identify all such strongly connected components in a given directed graph. We'll solve this using Kosaraju's Algorithm, which is efficient and beginner-friendly once understood step-by-step.

Step-by-Step Solution with Example

Step 1: Do a DFS on the original graph and record finish times

Start by doing a standard DFS traversal of the graph. As we finish exploring each node (i.e., all its neighbors are visited), we push it onto a stack. This stack captures the nodes in the order of their finishing times—the last finished node ends up on top.

Why? This helps us process nodes in the right order during the second DFS on the transposed graph.

Step 2: Transpose the graph (reverse all edges)

Next, we reverse all the directed edges in the graph. That is, if there was an edge from A → B, in the transposed graph it becomes B → A.

This reversal helps us discover which nodes can be reached in reverse direction, a key aspect in identifying SCCs.

Step 3: Do DFS on the transposed graph using the stack order

Now, we pop nodes one by one from the stack and perform DFS on the transposed graph. Each time we start a new DFS from an unvisited node, we find one SCC—all the nodes reached in this DFS form a strongly connected component.

Since the stack ensures we process nodes in decreasing order of finish times, we are guaranteed that whenever we start a new DFS, we start from a root node of some SCC.

Example: Step-by-step on a sample graph


Graph:
Vertices = {0, 1, 2, 3, 4}
Edges = {
  0 → 2,
  2 → 1,
  1 → 0,
  0 → 3,
  3 → 4
}

Step 1: DFS Finish Order (pushed to stack): [4, 3, 0, 1, 2]
Step 2: Transpose Graph:
  2 → 0
  1 → 2
  0 → 1
  3 → 0
  4 → 3

Step 3: DFS on Transposed Graph in Stack Order:
- Start DFS from 2 → reaches 2, 1, 0 → SCC1 = [2,1,0]
- Next node in stack is 1 → already visited
- Next is 0 → already visited
- Next is 3 → reaches 3 → SCC2 = [3]
- Next is 4 → reaches 4 → SCC3 = [4]

Final SCCs: [2,1,0], [3], [4]

Edge Cases

Empty Graph: No vertices means no SCCs to find.
Single Node: A single node with or without a self-loop is an SCC by itself.
Disconnected Nodes: Nodes with no outgoing or incoming edges form their own SCCs.
Multiple Cycles: Kosaraju's algorithm naturally groups cycles correctly into separate SCCs.

Finally

Kosaraju’s Algorithm is a powerful and intuitive method to identify strongly connected components. Its beauty lies in the simplicity of using two DFS traversals—first to record finish order, and second to explore reversed connectivity.

It runs in linear time O(V + E), making it suitable even for large graphs. As you work through the steps, always remember that SCCs are about mutual reachability, and DFS with finish order is the key to unlocking that structure.

Algorithm Steps❯

Initialize a visited array and an empty stack.
For each unvisited vertex, perform DFS and push the vertex onto the stack after visiting all its descendants.
Reverse all edges of the graph (create a transpose).
Reset the visited array.
While the stack is not empty:
1. Pop a vertex from the stack.
2. If it hasn't been visited, perform DFS from that node in the transposed graph.
3. Each such DFS traversal gives one strongly connected component.

Code

JavaScript

function kosarajuSCC(V, adj) {
  const visited = new Array(V).fill(false);
  const stack = [];

  function dfs(v) {
    visited[v] = true;
    for (let nei of adj[v] || []) {
      if (!visited[nei]) dfs(nei);
    }
    stack.push(v);
  }

  for (let i = 0; i < V; i++) {
    if (!visited[i]) dfs(i);
  }

  const transpose = Array.from({ length: V }, () => []);
  for (let u = 0; u < V; u++) {
    for (let v of adj[u] || []) {
      transpose[v].push(u);
    }
  }

  visited.fill(false);
  let count = 0;

  function reverseDFS(v) {
    visited[v] = true;
    for (let nei of transpose[v]) {
      if (!visited[nei]) reverseDFS(nei);
    }
  }

  while (stack.length > 0) {
    const node = stack.pop();
    if (!visited[node]) {
      reverseDFS(node);
      count++;
    }
  }

  return count;
}

// Example usage
const graph = {
  0: [1],
  1: [2],
  2: [0],
  3: [4]
};

console.log("Number of SCCs:", kosarajuSCC(5, graph)); // Output: 2

⬅ Previous TopicArticulation Points in Graphs

Next Topic ⮕Search Word in Trie

Comments

Loading comments...