jsschools

Kosaraju's Algorithm

Finds all strongly connected components (SCCs) in a directed graph using two DFS passes — one on the original graph to get finish-time order, and one on the transposed graph.

Spec ↗

Syntax

kosaraju(graph, V)

Parameters

NameTypeRequiredDescription
graph Map<number, number[]> Yes Directed adjacency list (0-indexed vertices).
V number Yes Number of vertices.

Returns

number[][] — Array of SCCs, each SCC being an array of vertex ids.

Examples

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

  function dfs1(u) {
    visited[u] = true;
    for (const v of graph.get(u) ?? []) if (!visited[v]) dfs1(v);
    stack.push(u);
  }

  // Pass 1: fill stack by finish time
  for (let i = 0; i < V; i++) if (!visited[i]) dfs1(i);

  // Build transposed graph
  const transposed = new Map(Array.from({length:V},(_,i)=>[i,[]]));
  for (const [u, ns] of graph) for (const v of ns) transposed.get(v).push(u);

  // Pass 2: DFS on transposed in reverse finish order
  visited.fill(false);
  const sccs = [];

  function dfs2(u, scc) {
    visited[u] = true;
    scc.push(u);
    for (const v of transposed.get(u) ?? []) if (!visited[v]) dfs2(v, scc);
  }

  while (stack.length) {
    const u = stack.pop();
    if (!visited[u]) { const scc = []; dfs2(u, scc); sccs.push(scc); }
  }
  return sccs;
}

const g = new Map([[0,[2,3]],[1,[0]],[2,[1]],[3,[4]],[4,[]]]);
console.log(kosaraju(g, 5).map(s => s.sort((a,b)=>a-b)));
Output 
[ [ 0, 1, 2 ], [ 3 ], [ 4 ] ]

// A graph where every vertex is its own SCC
function kosaraju(graph, V) {
  const vis = new Array(V).fill(false), stack = [];
  const dfs1 = u => { vis[u]=true; for(const v of graph.get(u)??[]) if(!vis[v]) dfs1(v); stack.push(u); };
  for(let i=0;i<V;i++) if(!vis[i]) dfs1(i);
  const T = new Map(Array.from({length:V},(_,i)=>[i,[]]));
  for(const[u,ns] of graph) for(const v of ns) T.get(v).push(u);
  vis.fill(false); const sccs=[];
  const dfs2=(u,s)=>{ vis[u]=true; s.push(u); for(const v of T.get(u)??[]) if(!vis[v]) dfs2(v,s); };
  while(stack.length){ const u=stack.pop(); if(!vis[u]){ const s=[]; dfs2(u,s); sccs.push(s); } }
  return sccs;
}

const dag = new Map([[0,[1]],[1,[2]],[2,[]]]);
console.log(kosaraju(dag, 3).length); // 3 SCCs
Output 
3

Notes

| Case | Time | Space | |---------|----------|-------| | Best | O(V + E) | O(V) | | Average | O(V + E) | O(V) | | Worst | O(V + E) | O(V) | Kosaraju uses two DFS passes and requires building the transposed graph, using O(V + E) extra space. Tarjan's SCC algorithm finds SCCs in a single DFS pass and is generally preferred. Both produce the same SCCs. SCCs represent groups of mutually reachable vertices — condensing them produces a DAG useful for dependency analysis.

See also