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

> Discover the JavaScript implementation of Kosaraju's algorithm for finding strongly connected components. Learn how two DFS passes and graph reversal achieve this decomposition.

- Repository: [Oleksii Trekhleb/javascript-algorithms](https://github.com/trekhleb/javascript-algorithms)
- Tags: how-to-guide
- Published: 2026-02-24

---

**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`](https://github.com/trekhleb/javascript-algorithms/blob/main/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`](https://github.com/trekhleb/javascript-algorithms/blob/main/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`](https://github.com/trekhleb/javascript-algorithms/blob/main/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`](https://github.com/trekhleb/javascript-algorithms/blob/main/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`](https://github.com/trekhleb/javascript-algorithms/blob/main/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`](https://github.com/trekhleb/javascript-algorithms/blob/main/stronglyConnectedComponents.js)** ([`src/algorithms/graph/strongly-connected-components/stronglyConnectedComponents.js`](https://github.com/trekhleb/javascript-algorithms/blob/main/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`](https://github.com/trekhleb/javascript-algorithms/blob/main/depthFirstSearch.js)** ([`src/algorithms/graph/depth-first-search/depthFirstSearch.js`](https://github.com/trekhleb/javascript-algorithms/blob/main/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`](https://github.com/trekhleb/javascript-algorithms/blob/main/Stack.js)** ([`src/data-structures/stack/Stack.js`](https://github.com/trekhleb/javascript-algorithms/blob/main/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`](https://github.com/trekhleb/javascript-algorithms/blob/main/Graph.js)** ([`src/data-structures/graph/Graph.js`](https://github.com/trekhleb/javascript-algorithms/blob/main/src/data-structures/graph/Graph.js)): Contains the `Graph` class with the `reverse()` method for graph transposition.

- **[`GraphVertex.js`](https://github.com/trekhleb/javascript-algorithms/blob/main/GraphVertex.js)** ([`src/data-structures/graph/GraphVertex.js`](https://github.com/trekhleb/javascript-algorithms/blob/main/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:

```javascript
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`](https://github.com/trekhleb/javascript-algorithms/blob/main/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`](https://github.com/trekhleb/javascript-algorithms/blob/main/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.