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❯

To find the strongly connected components (SCCs) of a directed graph, we can use Kosaraju's Algorithm. The algorithm works in three main steps:

Step 1: Perform a DFS traversal of the original graph and store the finish time of each vertex in a stack.
Step 2: Reverse all the edges of the graph to obtain the transpose graph.
Step 3: Perform DFS on the transpose graph using the vertices in the order defined by the stack. Each DFS tree in this phase gives one strongly connected component.

This approach ensures that the traversal in the transposed graph always starts from the root of an SCC, making it possible to extract all components correctly. Kosaraju’s Algorithm is efficient and runs in linear time O(V + E).

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