Topological Sort (Kahn's BFS)
Topological Sort Dfs: order the vertices of a DAG so every edge points forward. Kahn's algorithm uses in-degrees.
- 1 <= V <= 10⁴
- 0 <= E <= 10⁵
- Graph must be a DAG — a cycle means no valid order exists
Intuition
Topological sort kahn orders a DAG so every edge points forward, using in-degrees rather than recursion. The rule that drives it is almost a restatement of what topological order means:
- A vertex is ready to be output exactly when it has no remaining prerequisites — that is, when its in-degree reaches zero.
Start by counting incoming edges for every vertex. Those with none depend on nothing and can go first, in any order. Output one, then remove its outgoing edges by decrementing each target's in-degree. That removal may bring other vertices to zero, freeing them in turn, and the process ripples outward in waves.
What makes Kahn's especially useful is that cycle detection comes free. In a DAG every vertex eventually reaches in-degree zero, so all V come out. If the output is shorter, the remaining vertices are each still waiting on another — which is precisely a cycle. No colours, no recursion-stack tracking, just a count.
Compared with the DFS version, which records vertices on the way out of the recursion and reverses the result, Kahn's arrives at the same kind of order from the opposite direction: DFS works backward from sinks, Kahn's forward from sources.
The practical differences are worth stating. Kahn's is iterative, so it is safe on very deep graphs where recursion would overflow, and it validates the input as a side effect. The DFS version is shorter to write but needs a separate check to spot cycles.
Peel off vertices with no remaining prerequisites. In-degree zero means nothing blocks you; removing a vertex decrements its neighbours, which may free them in turn. The count check at the end doubles as cycle detection — a cycle can never reach in-degree zero, so the queue stalls early.
Approach
Before reading on: price up what counting everything costs here, then ask what one visit per cell or vertex would have to mark so nothing is counted twice. Aim for O(V + E) time and O(V) space.
Count incoming edges
Scan every adjacency list once, incrementing indeg[v] for each edge u → v. This count is the entire state — a vertex's readiness is fully described by how many prerequisites remain.
Queue every zero-in-degree vertex
Seed the queue with all vertices having no incoming edges. A DAG always has at least one; if the queue starts empty, the graph is entirely cyclic and the final count will say so.
Peel and relax in waves
Pop a vertex, append it to the order, and decrement the in-degree of each target. Any target reaching zero is newly unblocked and joins the queue — this rippling is what drives the sort forward.
Get cycle detection free
If the output holds fewer than V vertices, the leftovers are each waiting on another — a cycle. No extra state is needed, unlike the DFS version which requires grey/black colouring to detect the same thing.
Accept that the order is not unique
When several vertices sit at in-degree zero simultaneously, any of them may go next. Use a min-heap instead of a queue if the problem asks for the lexicographically smallest valid order.
Compare with the DFS version
DFS records vertices on the way out and reverses the result, working backward from sinks; Kahn's works forward from sources. Kahn's is iterative and self-validating, which makes it the safer choice on deep graphs.
Cost of the peeling
Every vertex is queued once and every edge relaxed once, giving O(V + E) time and O(V) space for the in-degree array, the queue and the output.
Solution & live demo
Common pitfalls
Not detecting the stall
return order
if len(order) < n:
return []
return orderA cyclic graph produces a partial order and the algorithm terminates quietly. Comparing the output length against n is the whole cycle test — no separate DFS colouring needed.
Enqueuing on every decrement
indeg[u] -= 1 q.append(u)
indeg[u] -= 1
if indeg[u] == 0:
q.append(u)A vertex with three prerequisites would enter the queue three times and be emitted before its dependencies are satisfied. It becomes ready only on the transition to zero.
Counting outgoing edges as in-degree
for u in range(n):
indeg[u] += len(adj[u])for u in range(n):
for v in adj[u]:
indeg[v] += 1In-degree counts edges arriving at a vertex. Counting the adjacency list's length measures out-degree, which inverts the dependency direction and yields a reversed or invalid order.
Edge cases
Fewer than V vertices are output; return empty / report failure.
Any is acceptable; queue order decides which one appears.
Every vertex starts at in-degree 0 — any permutation is valid.