Topological Sort (Kahn's Algorithm)
Topological sort orders the nodes of a DAG so that every edge points from earlier to later. It is the algorithm behind build-system dependency resolution, course-prerequisite scheduling, and pipelined computation. This snippet covers Kahn's BFS-based algorithm with indegree tracking, a DFS-based variant that produces the same order via post-order, and a cycle-detection variant that returns null when the graph is not acyclic.
681 views
7
function topologicalSort(graph) {
const indegree = new Map();
for (const node of Object.keys(graph)) indegree.set(node, 0);
for (const node of Object.keys(graph)) {
for (const next of graph[node]) {
indegree.set(next, (indegree.get(next) || 0) + 1);
}
}
const queue = [];
for (const [node, deg] of indegree) {
if (deg === 0) queue.push(node);
}
const order = [];
while (queue.length > 0) {
const node = queue.shift();
order.push(node);
for (const next of graph[node] || []) {
indegree.set(next, indegree.get(next) - 1);
if (indegree.get(next) === 0) queue.push(next);
}
}
return order;
}
const graph = { A: ['B', 'C'], B: ['D'], C: ['D'], D: [] };
console.log(topologicalSort(graph)); // ['A', 'B', 'C', 'D']Kahn's algorithm computes the indegree (incoming edges) of every node, queues every zero-indegree node, then repeatedly pops a node, appends it to the output, and decrements the indegree of each successor. A successor is queued the moment its indegree drops to zero. The output order respects every edge by construction. Time complexity is O(V + E) and the algorithm doubles as a cycle detector: if the output has fewer nodes than the graph, a cycle exists. This is the textbook DAG order generator.
2 more snippets in this entry are available for premium members.
Upgrade to Premium