Topological sort

Overview

A topological sort orders the vertices of a directed acyclic graph (DAG) so that for every edge u -> v, u comes before v. It answers 'in what order can I do these tasks when some depend on others?' If the graph has a cycle, no valid order exists, which is how you detect impossible dependency chains.

There are two standard algorithms. Kahn's algorithm (BFS) repeatedly removes nodes with in-degree 0. The DFS approach adds each node to the order after all its descendants finish, then reverses. Both run in O(V + E).

When to use it

• Prerequisites, dependencies, build order, task scheduling.
• Detect whether dependencies contain a cycle.
• DP on a DAG: longest path, number of paths, earliest completion time.
• Reconstruct an order from pairwise constraints (alien dictionary).

Problem patterns it solves

Where it is used in real software

Key terms

DAG

Directed acyclic graph: directed edges and no cycles.

In-degree

Number of incoming edges; in-degree 0 means no unmet dependencies.

Kahn's algorithm

BFS that repeatedly takes in-degree 0 nodes.

Reverse postorder

DFS finishing order, reversed, is a topological order.

Kahn's algorithm

1. 1
   Build the graph and in-degrees

   For prerequisite [a, b] (b before a): edge b -> a and indegree[a]++.

2. 2
   Queue every in-degree 0 node

   They have no remaining dependencies.

3. 3
   Pop a node and append it to the order

   It can be done now.

4. 4
   Decrease neighbors' in-degrees

   When a neighbor reaches 0, all its dependencies are done: enqueue it.

5. 5
   Check the count

   If the order contains fewer than V nodes, the remaining ones are in a cycle.

Course schedule with 4 courses

prerequisites = [[1,0], [2,0], [3,1], [3,2]] (0 before 1 and 2; 1 and 2 before 3)

All 4 courses were ordered, so there is no cycle. [0, 2, 1, 3] would also be valid: topological orders are usually not unique.

Implementation

1// 210. Course Schedule II with Kahn's algorithm2function findOrder(numCourses, prerequisites) {3  const graph = Array.from({ length: numCourses }, () => []);4  const indegree = new Array(numCourses).fill(0);5  for (const [course, pre] of prerequisites) {6    graph[pre].push(course);7    indegree[course]++;8  }9 10  const queue = [];11  for (let i = 0; i < numCourses; i++) if (indegree[i] === 0) queue.push(i);12 13  const order = [];14  for (let head = 0; head < queue.length; head++) {15    const node = queue[head];16    order.push(node);17    for (const next of graph[node]) {18      if (--indegree[next] === 0) queue.push(next);19    }20  }21  return order.length === numCourses ? order : []; // [] means a cycle22}23 24// DFS version: reverse postorder25function topoSortDFS(n, graph) {26  const state = new Array(n).fill(0); // 0 new, 1 visiting, 2 done27  const order = [];28  function visit(u) {29    if (state[u] === 1) throw new Error("cycle");30    if (state[u] === 2) return;31    state[u] = 1;32    for (const v of graph[u]) visit(v);33    state[u] = 2;34    order.push(u); // added after all descendants35  }36  for (let i = 0; i < n; i++) visit(i);37  return order.reverse();38}

Complexity and performance

Trade-offs

Variants and related techniques

Common mistakes

• Reversing edge direction.

  Fix: For [a, b] meaning b must come before a, the edge is b -> a.

• Returning a partial order when a cycle exists.

  Fix: Check order.length === V.

• Alien dictionary edge cases.

  Fix: A longer word appearing before its own prefix ("abc" before "ab") is invalid.

Interview questions

Practice problems