Introduction
Kosaraju's algorithm finds Strongly Connected Components (SCCs) in directed graphs. Understanding the theory is useful, but implementing the algorithm reveals why its two DFS passes and graph transpose work together.
In this article, we will implement Kosaraju using both JavaScript and TypeScript and examine the engineering details that matter beyond textbook pseudocode.
We will cover:
- adjacency-list graph representation
- the first DFS and finishing order
- constructing the transpose graph
- the second DFS
- a generic TypeScript implementation
- testing
- time and space complexity
- recursion limitations
- common implementation mistakes
Kosaraju in Three Steps
At a high level:
1. DFS on the original graph
2. Reverse every edge
3. DFS on the transpose using reverse finish orderConceptually:
Original Graph
↓
First DFS
↓
Finish Order
↓
Transpose Graph
↓
Second DFS
↓
SCCsConsider:
0 → 1
1 → 2
2 → 0
1 → 3
3 → 4
4 → 3The expected components are:
{0, 1, 2}
{3, 4}Representing the Graph in JavaScript
An adjacency list is a natural representation for sparse graphs:
const graph = new Map([
[0, [1]],
[1, [2, 3]],
[2, [0]],
[3, [4]],
[4, [3]]
]);Map is particularly useful because vertex identifiers do not have to be sequential integers.
First DFS: Building the Finish Order
The first DFS must add each vertex to the stack after all of its descendants have been processed.
function fillOrder(node, graph, visited, stack) {
visited.add(node);
for (const neighbor of graph.get(node) ?? []) {
if (!visited.has(neighbor)) {
fillOrder(neighbor, graph, visited, stack);
}
}
stack.push(node);
}The location of:
stack.push(node);is critical.
We need finishing order rather than discovery order.
The mental model is:
Enter vertex
↓
Explore descendants
↓
Finish vertex
↓
Push onto stackBecause a directed graph may be disconnected, DFS must be started from every still-unvisited vertex.
Constructing the Transpose Graph
The transpose of a directed graph reverses every edge.
A → Bbecomes:
B → AImplementation:
function transposeGraph(graph) {
const transpose = new Map();
for (const node of graph.keys()) {
transpose.set(node, []);
}
for (const [node, neighbors] of graph.entries()) {
for (const neighbor of neighbors) {
if (!transpose.has(neighbor)) {
transpose.set(neighbor, []);
}
transpose.get(neighbor).push(node);
}
}
return transpose;
}The SCC membership itself is preserved when all edges are reversed.
Second DFS: Collecting Components
The second DFS runs on the transposed graph.
function collectComponent(node, graph, visited, component) {
visited.add(node);
component.push(node);
for (const neighbor of graph.get(node) ?? []) {
if (!visited.has(neighbor)) {
collectComponent(neighbor, graph, visited, component);
}
}
}Each new DFS started according to the finishing stack identifies one SCC.
Complete JavaScript Implementation
function kosaraju(graph) {
const visited = new Set();
const stack = [];
function fillOrder(node) {
visited.add(node);
for (const neighbor of graph.get(node) ?? []) {
if (!visited.has(neighbor)) {
fillOrder(neighbor);
}
}
stack.push(node);
}
for (const node of graph.keys()) {
if (!visited.has(node)) {
fillOrder(node);
}
}
const transpose = new Map();
for (const node of graph.keys()) {
transpose.set(node, []);
}
for (const [node, neighbors] of graph.entries()) {
for (const neighbor of neighbors) {
if (!transpose.has(neighbor)) {
transpose.set(neighbor, []);
}
transpose.get(neighbor).push(node);
}
}
visited.clear();
const components = [];
function collectComponent(node, component) {
visited.add(node);
component.push(node);
for (const neighbor of transpose.get(node) ?? []) {
if (!visited.has(neighbor)) {
collectComponent(neighbor, component);
}
}
}
while (stack.length > 0) {
const node = stack.pop();
if (!visited.has(node)) {
const component = [];
collectComponent(node, component);
components.push(component);
}
}
return components;
}Test it with:
const graph = new Map([
[0, [1]],
[1, [2, 3]],
[2, [0]],
[3, [4]],
[4, [3]]
]);
console.log(kosaraju(graph));A possible result is:
[
[0, 2, 1],
[3, 4]
]The order inside an SCC is not important.
A Generic TypeScript Version
TypeScript allows us to describe the graph more precisely:
type Graph<T> = Map<T, T[]>;Now the implementation can support numbers, strings, or domain-specific identifiers.
type Graph<T> = Map<T, T[]>;
function kosaraju<T>(graph: Graph<T>): T[][] {
const visited = new Set<T>();
const stack: T[] = [];
const fillOrder = (node: T): void => {
visited.add(node);
for (const neighbor of graph.get(node) ?? []) {
if (!visited.has(neighbor)) {
fillOrder(neighbor);
}
}
stack.push(node);
};
for (const node of graph.keys()) {
if (!visited.has(node)) {
fillOrder(node);
}
}
const transpose: Graph<T> = new Map();
for (const node of graph.keys()) {
transpose.set(node, []);
}
for (const [node, neighbors] of graph.entries()) {
for (const neighbor of neighbors) {
if (!transpose.has(neighbor)) {
transpose.set(neighbor, []);
}
transpose.get(neighbor)!.push(node);
}
}
visited.clear();
const components: T[][] = [];
const collectComponent = (
node: T,
component: T[]
): void => {
visited.add(node);
component.push(node);
for (const neighbor of transpose.get(node) ?? []) {
if (!visited.has(neighbor)) {
collectComponent(neighbor, component);
}
}
};
while (stack.length > 0) {
const node = stack.pop()!;
if (!visited.has(node)) {
const component: T[] = [];
collectComponent(node, component);
components.push(component);
}
}
return components;
}Real Example: Microservice Dependencies
Consider this architecture:
user → payment
payment → notification
notification → user
report → analytics
analytics → report
admin → userWe can model it directly:
const services: Graph<string> = new Map([
["user", ["payment"]],
["payment", ["notification"]],
["notification", ["user"]],
["report", ["analytics"]],
["analytics", ["report"]],
["admin", ["user"]]
]);
console.log(kosaraju(services));Conceptually, the algorithm discovers:
["user", "payment", "notification"]
["report", "analytics"]
["admin"]The first two groups expose circular dependencies.
This is one way a theoretical graph algorithm can become an architecture-analysis tool.
Are Single-Vertex SCCs Valid?
Yes.
If a vertex does not belong to a larger strongly connected group, it forms an SCC by itself.
For:
A → Bwith no return path, the SCCs are:
{A}
{B}If your application only wants dependency cycles, you may filter components with more than one member.
const cycles = kosaraju(services).filter(
component => component.length > 1
);However, remember that a single vertex may contain a self-loop:
A → Awhich is also a cycle.
Time Complexity
The major operations are:
First DFS O(V + E)
Transpose O(V + E)
Second DFS O(V + E)Therefore:
Total = O(V + E)The constant number of linear passes does not change the asymptotic complexity.
Space Complexity
We store:
- the original adjacency list
- the transpose adjacency list
- visited state
- finishing stack
- result components
The overall auxiliary structure remains on the order of:
O(V + E)Recursion Depth in JavaScript
Recursive DFS is elegant and easy to understand, but JavaScript engines have limited call-stack depth.
A graph such as:
1 → 2 → 3 → 4 → ... → 500000can eventually cause:
RangeError: Maximum call stack size exceededFor very large or adversarial graphs, an iterative DFS implementation is safer.
A normal iterative DFS looks like:
function dfsIterative<T>(
start: T,
graph: Graph<T>
): Set<T> {
const visited = new Set<T>();
const stack: T[] = [start];
while (stack.length > 0) {
const node = stack.pop()!;
if (visited.has(node)) {
continue;
}
visited.add(node);
for (const neighbor of graph.get(node) ?? []) {
if (!visited.has(neighbor)) {
stack.push(neighbor);
}
}
}
return visited;
}Kosaraju's first pass is slightly more complicated because it requires true finishing order rather than ordinary traversal order.
Common Mistake: Missing Sink Vertices
Suppose the graph contains:
A → BIf we only write:
graph.set("A", ["B"]);then B might not exist as a key in the map.
A robust graph builder should register both endpoints:
graph.set("A", ["B"]);
graph.set("B", []);Common Mistake: Not Clearing visited
After the first DFS, every processed vertex remains in the visited set.
Before the second pass:
visited.clear();is mandatory.
Otherwise no SCCs will be explored during the second phase.
Common Mistake: Using Discovery Order
This is one of the most important implementation mistakes.
Incorrect:
visited.add(node);
stack.push(node);Correct:
visited.add(node);
for (...) {
...
}
stack.push(node);The algorithm needs post-order finishing information.
Common Mistake: Second DFS on the Original Graph
The second pass must traverse the transpose graph.
Running it on the original graph defeats the structural separation that Kosaraju relies on.
A Reusable Graph Class
For larger TypeScript applications, graph construction can be encapsulated:
class DirectedGraph<T> {
private adjacency = new Map<T, T[]>();
addVertex(vertex: T): void {
if (!this.adjacency.has(vertex)) {
this.adjacency.set(vertex, []);
}
}
addEdge(from: T, to: T): void {
this.addVertex(from);
this.addVertex(to);
this.adjacency.get(from)!.push(to);
}
getAdjacencyList(): Graph<T> {
return this.adjacency;
}
}This makes graph construction safer and easier to reuse.
Testing SCC Output
SCC ordering is not usually deterministic enough to compare raw arrays directly.
A normalization helper can sort both components and their members before assertions:
const normalize = <T extends string | number>(
components: T[][]
): string[] => {
return components
.map(component => [...component].sort().join(","))
.sort();
};This allows tests to verify set membership rather than accidental traversal order.
JavaScript or TypeScript?
The algorithmic logic is almost identical.
JavaScript is convenient for demonstrations and small scripts.
TypeScript becomes attractive in larger applications because it provides:
- type safety
- reusable generic graph types
- safer refactoring
- clearer APIs
- earlier detection of mistakes
For a production dependency analyzer or architecture tool, TypeScript is often the better fit.
When Is Kosaraju a Good Choice?
Kosaraju is appropriate when:
- the input is a directed graph
- every SCC must be discovered
- implementation clarity matters
- storing or generating a transpose graph is acceptable
- linear
O(V + E)complexity meets the requirements
When additional memory for the transpose is undesirable, algorithms such as Tarjan may also be worth considering.
Mental Model
A compact way to remember Kosaraju is:
First DFS:
Find the finishing order
↓
Reverse all edges
↓
Second DFS:
Follow reverse finish order
↓
Each DFS tree reveals one SCCConclusion
We implemented Kosaraju's algorithm with both JavaScript and TypeScript.
The essential steps are:
- represent the directed graph with an adjacency list
- run DFS and record finishing order
- build the transpose graph
- reset visited state
- process vertices in reverse finishing order
- collect one SCC per DFS traversal
The algorithm runs in:
O(V + E)time with adjacency lists and requires linear graph storage.
More importantly, the implementation can be applied directly to practical problems such as detecting circular dependencies between modules, packages, or microservices.
The key implementation idea is:
The first DFS determines the correct processing order, the transpose reverses reachability between SCCs, and the second DFS exposes the component boundaries.
A natural next step is to compare this implementation with Tarjan's algorithm or build an iterative production-oriented version that avoids JavaScript recursion limits.