Topological Sort

Graphs

avgO(V + E)worstO(V + E)spaceO(V)

Start every in-degree at 0, then count each node's incoming edges

1 / 33

Code

function topologicalSort(graph: Graph) {  const indegree = new Array(graph.size).fill(0);  for (const { to } of graph.edges) indegree[to]++;  const queue = graph.nodes.filter((v) => indegree[v] === 0);  const order: number[] = [];  while (queue.length > 0) {    const node = queue.shift()!;    order.push(node);    for (const next of graph.neighbours(node)) {      indegree[next]--;      if (indegree[next] === 0) queue.push(next);    }  }  // Leftover nodes all wait on each other: they sit on a cycle.  if (order.length < graph.size) throw new Error("graph has a cycle");  return order;}

procedure TopologicalSort(G)    ▷ Kahn's algorithm  indegree[v] ← 0 for every node v  for each edge (u → v) do indegree[v] ← indegree[v] + 1  queue ← every node with indegree 0  order ← []  while queue is not empty do    node ← dequeue(queue)    append node to order    for each edge (node → next) do    ▷ remove the edge      indegree[next] ← indegree[next] − 1      if indegree[next] = 0 then enqueue(queue, next)    end for  end while  ▷ leftover nodes wait on each other: a cycle  if order is missing nodes then fail: G has a cycle  return orderend procedure

Variables

none

Counters

processed: 0
edges removed: 0

Nodes8

Source

Edges (directed: A>B)

How it works

Kahn's algorithm orders a directed acyclic graph so every edge points forward: it repeatedly outputs a node with no remaining incoming edges and deletes that node's outgoing edges. Each in-degree that drops to zero releases a new node into the queue; if the queue empties early, the graph has a cycle.

Complexity

Best: O(V + E)
Average: O(V + E)
Worst: O(V + E)
Space: O(V)

Node	In-degree	Status
A	0	waiting
B	0	waiting
C	0	waiting
D	0	waiting
E	0	waiting
F	0	waiting
G	0	waiting
H	0	waiting

Topological Sort

How it works

Complexity

Search algorithms