Topological sort: three ways, and when each breaks

Topological sort is the graph problem most likely to appear disguised. Course schedules, build systems, task dependencies, formula evaluation — all the same question: is there an order respecting every 'must come before' constraint, and if so, what is it?

Kahn's algorithm

Count incoming edges. Anything with a count of zero has no unmet prerequisites, so it can go next. Emit it, decrement its neighbours, and enqueue any that just reached zero.

python

1from collections import deque

3def topo(n, edges):

4 graph = [[] for _ in range(n)]

5 indeg = [0] * n

6 for u, v in edges: # u must come before v

7 graph[u].append(v)

8 indeg[v] += 1

10 q = deque(i for i in range(n) if indeg[i] == 0)

11 order = []

12 while q:

13 u = q.popleft()

14 order.append(u)

15 for v in graph[u]:

16 indeg[v] -= 1

17 if indeg[v] == 0:

18 q.append(v)

20 return order if len(order) == n else [] # short means a cycle

Free cycle detection

If the output is shorter than n, the leftover nodes are exactly those stuck in or behind a cycle. You get cycle detection without writing any.

DFS with three colours

The alternative: depth-first search, pushing each node onto an output list after all its descendants are done, then reversing. Cycle detection needs three states, not two.

→White — not visited.
→Grey — on the current recursion stack.
→Black — fully finished.

An edge into a grey node is a back edge, which means a cycle. An edge into a black node is fine — that subtree is already ordered. Using a single visited boolean conflates grey and black, and that is the bug: it reports cycles on ordinary diamond-shaped DAGs.

python

1WHITE, GREY, BLACK = 0, 1, 2

3def topo_dfs(n, graph):

4 color = [WHITE] * n

5 order = []

7 def visit(u):

8 if color[u] == GREY:

9 return False # back edge: cycle

10 if color[u] == BLACK:

11 return True # already done

12 color[u] = GREY

13 for v in graph[u]:

14 if not visit(v):

15 return False

16 color[u] = BLACK

17 order.append(u)

18 return True

20 for u in range(n):

21 if not visit(u):

22 return []

23 return order[::-1]

The naive attempt

Sort by in-degree once and emit in that order. It looks reasonable and is wrong: in-degree changes as nodes are removed. A node with in-degree 3 whose three prerequisites are all first in line is perfectly valid to schedule fourth, and a static sort has no way to express that.

Which to use

→Kahn's — when you want an iterative solution, need cycle detection anyway, or want lexicographically smallest order (swap the queue for a heap).
→DFS — when you already have a DFS, or want strongly connected components next, since the finish order feeds directly into Kosaraju's algorithm.
→Either — the complexity is O(V + E) both ways.

One caution

The DFS version recurses to graph depth. On a path-shaped dependency graph of 10^5 nodes that is 10^5 frames. On large inputs prefer Kahn's, or convert the DFS to an explicit stack.

graphtopological-sortdfs

Practise this

Reading about a pattern is not the same as producing it under time pressure. The problems that drill this are in the curriculum, in order.

open_curriculum create_account

previousUnion-Find: the two optimisations and why both matter next Memory is a complexity too, and you are probably not counting it