Home/Graphs/Topological sort
Search algorithmsCTRL K

Topological sort

· DAG · every dependency before its dependents
/graphs/topological-sort
PLACED
0/ 10
nodes in the order
QUEUE
0
nodes with in-degree 0
EDGES
0/ 16
processed
CURRENT
—
node being placed
ORDER
the sequence so far
being placedin-degree 0 · edge removedplacedwaiting on edges
10 nodes · 16 edges · seed 7 · 29 steps
step 0 / 28
Nodes10
topological_sort.ts
1
function topologicalSort(graph: DAG) {
2
  const inDegree = new Map(graph.nodes.map((node) => [node, 0]));
3
  for (const [source, successor] of graph.edges) inDegree.set(successor, inDegree.get(successor)! + 1);
4
  const queue = graph.nodes.filter((node) => inDegree.get(node) === 0);
5
  const order: Node[] = [];
6
  while (queue.length > 0) {
7
    const node = queue.shift()!;
8
    order.push(node);
9
    for (const successor of graph.successors(node)) {
10
      inDegree.set(successor, inDegree.get(successor)! - 1);
11
      if (inDegree.get(successor) === 0) queue.push(successor);
12
    }
13
  }
14
  return order;
15
}
CURRENT STEP
line 3

Count the incoming edges of every node: A:0 B:1 C:1 D:1 E:4 F:1 G:1 H:1 I:3 J:3.

// how it works

Understanding Topological sort

topological sort · what order do the tasks go in
01

The idea

Kahn's algorithm orders the nodes of a directed acyclic graph so that every edge points forward. It counts the incoming edges of each node, starts with the nodes that have none, and repeatedly takes one, appends it to the order, and removes its outgoing edges. Whenever a node's count drops to zero, it becomes available.

If the graph has a cycle the queue empties before every node is placed: no order exists. That makes the same loop a cycle detector, which is how build systems, package managers and spreadsheets refuse circular dependencies.

02

The four stages

1
countin-degree of every node
2
sourcesin-degree 0 go into the queue
3
placedequeue one, append to the order
4
releaseremove its edges; new zeros join the queue
03

Complexity

best
O(V + E)every node and edge once
average
O(V + E)linear in the size of the graph
worst
O(V + E)a cycle stops it early, still linear
space
O(V)queue and in-degrees
04

Versus its siblings

EDGES PROCESSED · 1 000 TASKS, 3 000 DEPENDENCIES
kahn
3,000
dfs post-order
3,000
longest path (dp)
3,000
cycle check only
3,000
naive source scan
3M
both linear methods give a valid order; the naive one rescans every node per step
05

Pseudocode

KAHN(graph)
  inDegree[node] ← number of edges into node, for every node
  queue ← every node with inDegree[node] = 0; order ← []
  while queue not empty
    node ← dequeue; append node to order
    for each edge node → successor: inDegree[successor] ← inDegree[successor] − 1; if 0: enqueue successor
  if |order| < |V|: the graph has a cycle
06

When to use

Dependency resolution: build steps, package installs, spreadsheet cells, course prerequisites.
Scheduling with precedence constraints, and as the first pass of dynamic programming over a DAG.
07

Pitfalls

A cycle leaves nodes unplaced; check that the order has V nodes, or you silently drop tasks.
Many valid orders exist; if determinism matters, use a priority queue instead of a plain queue.
Modifying in-degrees of a shared graph makes the routine non-reentrant; copy the counts.
08

History

Arthur Kahn published this algorithm in 1962 for scheduling large projects with PERT networks. Tarjan gave the depth-first alternative in 1976, and every build system since make in 1976 has been, at its heart, a topological sort of a dependency graph.

Back to Graphs