Topological Sort

How topological sort works (Kahn's algorithm)

Kahn's algorithm is the more intuitive of the two. The idea: a vertex with no incoming edges (in-degree 0) has no prerequisites, so it can come first. Once we pick it, removing it from the graph may free up new vertices whose only remaining prerequisite was this one. Repeat until the graph is empty.

1. Compute the in-degree of every vertex.
2. Initialize a queue with all in-degree-0 vertices.
3. While the queue isn't empty: dequeue a vertex, append it to the output, decrement the in-degree of each of its neighbors. If a neighbor's in-degree drops to 0, enqueue it.
4. If the output has all V vertices, return it. Otherwise the graph has a cycle and no valid topological sort exists.

DFS-based topological sort

The DFS-based version uses finish times. Run DFS from each vertex; when DFS finishes processing a vertex (all its descendants have been visited), push it onto a stack. After the DFS completes, reverse the stack — that's the topological order.

The intuition: in DFS, a vertex finishes only after all its descendants finish. So in finish-time order, descendants finish before their ancestors. Reverse it, and ancestors come before descendants — which is exactly the topological order.

function topoSortDFS(graph) {
  const visited = new Set();
  const order = [];
  function dfs(node) {
    if (visited.has(node)) return;
    visited.add(node);
    for (const neighbor of graph[node] || []) dfs(neighbor);
    order.push(node); // finish — push when leaving
  }
  for (const node of Object.keys(graph)) dfs(node);
  return order.reverse();
}

Kahn's vs DFS-based

	Kahn's algorithm	DFS-based
Time	O(V + E)	O(V + E)
Space	O(V) — queue + in-degree array	O(V) — recursion stack + visited
Cycle detection	Natural — count of processed vs total	Natural — back-edge detection during DFS
Order produced	Sources first — BFS-ish	Sinks pushed first, reversed at end
Parallelizable	Yes — can extract all in-degree-0 vertices simultaneously	Sequential by nature
Stack overflow risk	None (iterative)	Yes (deep DAGs)
Best for	Build systems wanting parallelism	Educational, clean recursion

Real build systems use Kahn's because the "in-degree 0" set tells you what can run in parallel right now. DFS-based is simpler to write but doesn't expose parallelism naturally.

When to use topological sort

• Build systems and task schedulers. Make, Bazel, Gradle, npm, Maven — all use topological sort to determine compile and link order. Parallel builds use Kahn's to identify tasks with all dependencies satisfied.
• Course prerequisite scheduling. Each course is a vertex; "course A is a prereq for course B" is an edge from A to B. Topological sort produces a valid order to take them.
• Spreadsheet recalculation. Cells with formulas form a DAG of dependencies. Topological sort gives the order to recalculate after a change.
• Symbol resolution in compilers and linkers. Module imports form a DAG. Topological sort gives the linking order so each module's symbols are defined when it's loaded.
• Pre-processing for DP on DAGs. Many DP problems on DAGs (longest path, count paths, shortest with negative weights) require processing vertices in topological order so subproblems are solved first.

JavaScript — Kahn's algorithm

function topoSortKahn(graph) {
  // graph is an adjacency list: { 'A': ['B', 'C'], 'B': ['D'], ... }
  const inDegree = new Map();
  const allNodes = new Set(Object.keys(graph));

  // Compute in-degrees
  for (const node of Object.keys(graph)) {
    if (!inDegree.has(node)) inDegree.set(node, 0);
    for (const neighbor of graph[node]) {
      allNodes.add(neighbor);
      inDegree.set(neighbor, (inDegree.get(neighbor) || 0) + 1);
    }
  }
  for (const node of allNodes) if (!inDegree.has(node)) inDegree.set(node, 0);

  // Queue all in-degree-0 vertices
  const queue = [...allNodes].filter(n => inDegree.get(n) === 0);
  const result = [];

  while (queue.length) {
    const node = queue.shift();
    result.push(node);
    for (const neighbor of graph[node] || []) {
      inDegree.set(neighbor, inDegree.get(neighbor) - 1);
      if (inDegree.get(neighbor) === 0) queue.push(neighbor);
    }
  }

  if (result.length !== allNodes.size) {
    throw new Error('Cycle detected — no valid topological order');
  }
  return result;
}

For better performance on large graphs, replace queue.shift() with a head pointer or use collections.deque in Python — shift() is O(n) in JavaScript.

Python implementation

from collections import deque, defaultdict

def topo_sort(graph):
    in_degree = defaultdict(int)
    all_nodes = set(graph.keys())
    for node in graph:
        for neighbor in graph[node]:
            in_degree[neighbor] += 1
            all_nodes.add(neighbor)
    for node in all_nodes:
        in_degree.setdefault(node, 0)

    queue = deque(n for n in all_nodes if in_degree[n] == 0)
    result = []
    while queue:
        node = queue.popleft()
        result.append(node)
        for neighbor in graph.get(node, []):
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    if len(result) != len(all_nodes):
        raise ValueError('Cycle detected')
    return result

Famous topological sort problems

Course Schedule (LeetCode 207, 210)

Given n courses and a list of prerequisites, can you complete all courses? (And: in what order?) Build the prerequisite graph and run Kahn's. If all n courses end up in the topological order, you can complete them; the order itself is your answer.

Alien Dictionary

Given a list of words sorted in some unknown alphabetical order, derive the alphabet. Compare adjacent words to find the first differing character; that gives an edge "earlier letter → later letter" in the alphabet's ordering DAG. Topological-sort the resulting graph to get the alphabet — or detect a cycle, meaning the input is inconsistent.

Parallel Build Scheduling

// Returns groups of tasks that can run in parallel, in order
function parallelBatches(graph) {
  const inDegree = new Map();
  const allNodes = new Set(Object.keys(graph));
  for (const node of Object.keys(graph)) {
    inDegree.set(node, inDegree.get(node) || 0);
    for (const neighbor of graph[node]) {
      allNodes.add(neighbor);
      inDegree.set(neighbor, (inDegree.get(neighbor) || 0) + 1);
    }
  }
  for (const node of allNodes) if (!inDegree.has(node)) inDegree.set(node, 0);

  const batches = [];
  let current = [...allNodes].filter(n => inDegree.get(n) === 0);

  while (current.length) {
    batches.push(current);
    const next = [];
    for (const node of current) {
      for (const neighbor of graph[node] || []) {
        inDegree.set(neighbor, inDegree.get(neighbor) - 1);
        if (inDegree.get(neighbor) === 0) next.push(neighbor);
      }
    }
    current = next;
  }
  return batches;
}

Each batch contains tasks that can all run simultaneously. Build systems use this to maximize parallelism — running each batch as a parallel pool of jobs.

Common bugs and edge cases

• Forgetting to count vertices reached. If the input graph has a cycle, the algorithm doesn't crash — it just produces a partial result. Always check that the output has all V vertices; raise an error if not.
• Missing vertices that have no edges. Vertices with in-degree 0 AND out-degree 0 might be missing from the adjacency list. Track them explicitly via a set of all known vertices.
• Mutating in-degrees of the input. If you decrement in-degrees of a graph the caller still uses, you've trashed their data. Either copy the in-degrees or document the mutation.
• Treating undirected graphs as DAGs. Topological sort is meaningless for undirected graphs. If the input has bidirectional edges, every pair forms a 2-cycle and no topological order exists.
• Slow queue operations. JavaScript's arr.shift() is O(n). On a graph with 100k vertices, that's 100k × 100k = 10 billion operations vs the algorithm's O(V + E). Use a deque or maintain a head index.