Topological Sort Pattern

When to use Topological Sort

• The input describes dependencies between tasks, courses, items, or jobs ("X must come before Y").
• You need to detect whether a directed graph contains a cycle.
• You need a build order, install order, or compile order for an interlinked set of modules.
• You need to schedule tasks subject to prerequisite constraints.
• You need to reconstruct a partial order from a list of pairwise comparisons (alien dictionary).

Template

function topologicalSort(numNodes, edges) {
  const indegree = new Array(numNodes).fill(0);
  const graph = Array.from({ length: numNodes }, () => []);
  for (const [from, to] of edges) {
    graph[from].push(to);
    indegree[to]++;
  }
  const queue = [];
  for (let i = 0; i < numNodes; i++) {
    if (indegree[i] === 0) queue.push(i);
  }
  const order = [];
  while (queue.length > 0) {
    const node = queue.shift();
    order.push(node);
    for (const next of graph[node]) {
      if (--indegree[next] === 0) queue.push(next);
    }
  }
  return order.length === numNodes ? order : [];
}

Common mistakes

• Reversing the edge direction by mistake — the pattern needs `prerequisite -> course`, not the other way around (or vice versa, depending on the problem statement).
• Returning a partial order when a cycle exists; the algorithm must detect that fewer than V nodes were emitted and return an empty result or signal failure.
• Forgetting to initialize the indegree array to zero before counting, leaving undefined values in some languages.
• Using DFS post-order without a visited-state machine (unvisited / in-progress / done), which both misses cycles and double-counts nodes.
• Mutating the input edges list during processing, which makes the algorithm non-idempotent and breaks retry logic.