Topological Sort
Linear ordering of vertices in a directed acyclic graph.
How it works
Topological Sort produces a linear ordering of vertices in a Directed Acyclic Graph (DAG) such that for every directed edge u → v, vertex u appears before v in the result. Kahn's algorithm achieves this by repeatedly removing nodes whose in-degree has dropped to zero and enqueuing their successors.
The algorithm maintains an in-degree counter for each node and a queue of "ready" nodes (those with no remaining prerequisites). Each removal from the queue represents one resolved dependency — the node is appended to the result and its outgoing edges are relaxed.
If the result contains fewer nodes than the graph has vertices, a cycle exists and no valid ordering is possible — the algorithm serves as a cycle detector for directed graphs.
Complexity
Visualizer
Where it's used in the real world
Build systems (Make / Bazel / Gradle)
Task scheduling with dependenciesBefore compiling a target, all its dependencies must already be compiled. Topological sort determines the safe build order so no target is processed before its prerequisites.
Package managers (npm / pip / Cargo)
Dependency resolution and install orderWhen installing packages, each dependency must be installed before the packages that require it. A topo sort of the dependency graph gives the correct install sequence.
Database query planners (PostgreSQL / MySQL)
Scheduling joins and subquery evaluationQuery optimizers model subquery dependencies as a DAG and use topological ordering to determine which subresults must be materialized before downstream operations can execute.
Implementation
function topologicalSort(graph: Map<string, string[]>): string[] | null {
const inDegree = new Map<string, number>();
for (const [node, neighbors] of graph) {
if (!inDegree.has(node)) inDegree.set(node, 0);
for (const nb of neighbors) {
inDegree.set(nb, (inDegree.get(nb) ?? 0) + 1);
}
}
const queue: string[] = [];
for (const [node, deg] of inDegree) {
if (deg === 0) queue.push(node);
}
const result: string[] = [];
while (queue.length > 0) {
const u = queue.shift()!;
result.push(u);
for (const v of graph.get(u) ?? []) {
const newDeg = (inDegree.get(v) ?? 0) - 1;
inDegree.set(v, newDeg);
if (newDeg === 0) queue.push(v);
}
}
// If result doesn't include every node, a cycle exists
return result.length === inDegree.size ? result : null;
}