Strongly Connected Components (Kosaraju's Algorithm) Implementation in JavaScript

Kosaraju’s algorithm in the javascript-algorithms repository uses two depth-first search passes and a graph reversal to decompose a directed graph into strongly connected components, implemented in stronglyConnectedComponents.js.

The trekhleb/javascript-algorithms repository provides a production-ready implementation of Kosaraju’s algorithm for finding strongly connected components (SCCs) in directed graphs. This solution leverages the repository’s generic graph data structures and depth-first search utilities to identify maximal subsets of vertices where each vertex is reachable from every other vertex in the subset.

Algorithm Architecture

The implementation follows the classic two-pass DFS strategy defined in src/algorithms/graph/strongly-connected-components/stronglyConnectedComponents.js. The algorithm orchestrates three distinct phases: ordering vertices by finish time, transposing the graph, and extracting components.

Pass One: Ordering by Finish Time

The function getVerticesSortedByDfsFinishTime performs the initial DFS traversal on the original graph to establish processing order. It utilizes the generic depthFirstSearch utility from src/algorithms/graph/depth-first-search/depthFirstSearch.js with custom callbacks:

• enterVertex: Marks vertices as visited upon entry.
• leaveVertex: Pushes vertices onto a Stack instance (from src/data-structures/stack/Stack.js) when DFS finishes exploring all descendants.
• allowTraversal: Prevents revisiting already visited vertices.

This ensures the vertex finished last in the recursion appears at the top of the stack, establishing the reverse finish-time order required for the second pass.

Graph Transposition

Between passes, the algorithm calls graph.reverse() (implemented in src/data-structures/graph/Graph.js) to compute the transpose graph. This method removes all directed edges, flips their direction, and re-adds them, effectively reversing every edge in the original graph while preserving the vertex set.

Pass Two: Component Extraction

The getSCCSets function executes the second DFS pass on the reversed graph. It pops vertices from the finish-time stack one by one; each unvisited vertex initiates a new DFS traversal. The DFS callbacks collect all reachable vertices into a temporary stronglyConnectedComponentsSet. When the traversal completes (indicated by previousVertex === null in the callback), the collected set represents one complete strongly connected component. The function accumulates these sets into the final result array.

Core Source Files and Functions

The implementation spans multiple modules to maintain separation of concerns:

• stronglyConnectedComponents.js (src/algorithms/graph/strongly-connected-components/stronglyConnectedComponents.js): Exports the default stronglyConnectedComponents function that orchestrates the two-pass algorithm and returns the array of SCCs.

• depthFirstSearch.js (src/algorithms/graph/depth-first-search/depthFirstSearch.js): Provides the generic depthFirstSearch utility used for both traversal passes with configurable enterVertex, leaveVertex, and allowTraversal callbacks.

• Stack.js (src/data-structures/stack/Stack.js): Implements the Stack class used to store vertices in finish-time order between the first and second passes.

• Graph.js (src/data-structures/graph/Graph.js): Contains the Graph class with the reverse() method for graph transposition.

• GraphVertex.js (src/data-structures/graph/GraphVertex.js): Defines the GraphVertex class representing individual vertices stored in the SCC result sets.

Practical Usage Example

The following example demonstrates how to construct a directed graph, execute the algorithm, and interpret the results:

import Graph from '../data-structures/graph/Graph';
import GraphVertex from '../data-structures/graph/GraphVertex';
import GraphEdge from '../data-structures/graph/GraphEdge';
import stronglyConnectedComponents from '../algorithms/graph/strongly-connected-components/stronglyConnectedComponents';

// 1️⃣ Build a directed graph
const graph = new Graph(true);  // true indicates directed graph

// Create vertices
const vA = new GraphVertex('A');
const vB = new GraphVertex('B');
const vC = new GraphVertex('C');
const vD = new GraphVertex('D');
const vE = new GraphVertex('E');

// Add vertices to the graph
[vA, vB, vC, vD, vE].forEach(v => graph.addVertex(v));

// Add directed edges (A→B, B→C, C→A form one SCC; D→E is separate)
graph
  .addEdge(new GraphEdge(vA, vB))
  .addEdge(new GraphEdge(vB, vC))
  .addEdge(new GraphEdge(vC, vA))
  .addEdge(new GraphEdge(vD, vE));

// 2️⃣ Run Kosaraju’s SCC algorithm
const sccs = stronglyConnectedComponents(graph);

// 3️⃣ Inspect the results
sccs.forEach((component, idx) => {
  const names = component.map(v => v.getKey()).join(', ');
  console.log(`Component ${idx + 1}: ${names}`);
});

/*
Expected output:
Component 1: A, B, C
Component 2: D
Component 3: E
*/

In this example, vertices A, B, and C form a cycle and thus constitute one strongly connected component. Vertex D and E form separate singleton components because neither can reach the other bidirectionally.

Summary

• Kosaraju’s algorithm in javascript-algorithms implements the classic two-pass DFS approach to find strongly connected components in O(V + E) time complexity.
• The first pass uses getVerticesSortedByDfsFinishTime to order vertices by completion time using a Stack.
• Graph reversal is handled by the reverse() method in the Graph class, creating the transpose graph required for the second pass.
• The second pass (getSCCSets) processes vertices in reverse finish-time order on the transposed graph to isolate individual SCCs.
• The implementation returns an array of arrays, where each inner array contains GraphVertex objects representing one strongly connected component.

Frequently Asked Questions

What is the time and space complexity of this Kosaraju’s implementation?

According to the source code analysis, the algorithm runs in O(V + E) time, where V is the number of vertices and E is the number of edges. This is because each DFS pass visits every vertex and edge exactly once. The space complexity is O(V) to store the recursion stack, the finish-time Stack, and the visited markers.

How does the graph reversal work in the JavaScript implementation?

The Graph class in src/data-structures/graph/Graph.js provides the reverse() method, which iterates through all edges, removes them from the graph, swaps their start and end vertices, and re-adds them with reversed direction. This creates the transpose graph in-place, which is essential for the second DFS pass to correctly identify strongly connected components.

Why does the algorithm use a custom Stack for the first DFS pass?

The implementation uses the Stack class from src/data-structures/stack/Stack.js to record the finish order of vertices. By pushing vertices onto the stack when the leaveVertex callback fires (after all descendants are processed), the stack naturally orders vertices from last-finished to first-finished. Popping from this stack in the second pass ensures vertices are processed in the correct reverse order, guaranteeing that each DFS tree in the transposed graph corresponds to exactly one strongly connected component.

Can this implementation handle disconnected graphs?

Yes. The algorithm naturally handles disconnected graphs because the first DFS pass (via depthFirstSearch with allowTraversal checks) visits all vertices regardless of connectivity, and the second pass processes every vertex in the finish-time stack. Each disconnected region will form its own strongly connected components or singletons in the final result array.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}