Topological Sort
Do whatever has no blockers left, then unblock the rest.
- Brute force
- O(V!) — try every ordering
- With the pattern
- O(V + E) — each node and edge handled once
- Extra space
- O(V + E) — graph + in-degree array
In plain English
“Getting dressed: socks before shoes, shirt before tie. You look at the pile and put on anything nothing else must come before. Each time you put something on, other items become free to wear. If you end up stuck with clothes left and every one still waiting on another, your rules contain a loop.”
Why it's fast
Trying all orderings is factorial. Kahn's algorithm tracks each node's in-degree (number of unmet prerequisites). Nodes at 0 are ready; finishing one decrements its dependents. Each edge is processed once, so it's O(V + E) — and if fewer than V nodes ever reach 0, there's a cycle.
Spot it when the problem says…
- prerequisites / dependencies
- can you finish all courses
- valid build / task order
- detect a cycle in a directed graph
- a must come before b
- recipes / ingredients that unlock others
Visualize
Course order with Kahn's algorithm
6 courses, edges a → b mean 'take a before b'. Find a valid order (or detect a cycle).
queue (ready: in-degree 0)
order
Count prerequisites per course (in-degree). A course with in=0 has nothing blocking it.
1from collections import deque2def topo_order(n, edges):3 graph = [[] for _ in range(n)]4 indegree = [0] * n5 for a, b in edges: # a must come before b6 graph[a].append(b)7 indegree[b] += 18 queue = deque(i for i in range(n) if indegree[i] == 0)9 order = []10 while queue:11 node = queue.popleft()12 order.append(node)13 for nxt in graph[node]:14 indegree[nxt] -= 115 if indegree[nxt] == 0:16 queue.append(nxt)17 return order if len(order) == n else [] # [] = cycleHow to apply it
- 01Build the adjacency list
prereq -> [dependents]and anindegreearray. - 02Queue every node with
indegree == 0. - 03Pop a node, append it to the order, decrement each dependent's in-degree; queue any that hit 0.
- 04If the order contains all V nodes it's valid; otherwise a cycle exists.
Variations you'll meet
Kahn's algorithm (Course Schedule II)
The visualizer's example.
from collections import dequedef find_order(n: int, prerequisites: list[list[int]]) -> list[int]: graph = [[] for _ in range(n)] indeg = [0] * n for course, pre in prerequisites: graph[pre].append(course) indeg[course] += 1 q = deque(i for i in range(n) if indeg[i] == 0) order = [] while q: u = q.popleft() order.append(u) for v in graph[u]: indeg[v] -= 1 if indeg[v] == 0: q.append(v) return order if len(order) == n else []DFS with three colours
0 = unvisited, 1 = on the current path, 2 = done. Seeing a 1 again means a cycle; reverse post-order is a topo order.
def can_finish(n: int, prerequisites: list[list[int]]) -> bool: graph = [[] for _ in range(n)] for course, pre in prerequisites: graph[pre].append(course) state = [0] * n def dfs(u: int) -> bool: # True if no cycle if state[u]: return state[u] == 2 state[u] = 1 if not all(dfs(v) for v in graph[u]): return False state[u] = 2 return True return all(dfs(i) for i in range(n))Longest path in a DAG
Process in topo order and relax dist[v] = max(dist[v], dist[u] + w) — Parallel Courses III.
Common mistakes
- Reversing the edge direction (
course -> preinstead ofpre -> course). - Forgetting isolated nodes with no edges — they still need to be in the order.
- Using a plain visited set for cycle detection in DFS; a directed graph needs the 'on current path' state.
- Returning a partial order instead of
[]when a cycle exists.
Practice ladder
Easy → hard. Tick them off as you go.
Think you've got it?
Let the AI interviewer throw a Topological Sort problem at you and grade how you explain it.