Ordering
Order tasks so every dependency comes before its dependents.
The idea
On a directed acyclic graph, a topological order lists vertices so every edge points forward. Kahn's algorithm repeatedly removes zero-in-degree nodes; DFS post-order reversed gives the same result. A cycle makes any ordering impossible.
The visualization tracks each vertex's remaining in-degree, the queue of ready-to-place vertices, and the emitted order — so you can see prerequisites melting away one edge at a time.
Getting dressed: socks before shoes, shirt before jacket. Independent items can go in any order, but the constraints impose a partial order.
When to reach for it
- Ordering tasks with prerequisites.
- Detecting cycles in dependencies.
- Compilation / build ordering.
Language-independent template
queue = [v for v if indeg[v]==0]
while queue:
u = queue.pop(); order.append(u)
for w in adj[u]:
indeg[w] -= 1
if indeg[w]==0: queue.append(w)Complexity — time O(V + E), space O(V).
Common mistakes
- Not detecting cycles (no valid order).
- Wrong in-degree bookkeeping in Kahn's.
- Forgetting reversal in the DFS variant.
Practice progression
Canonical interview problems, ordered from foundation to advanced application.
Find the person trusted by everyone who trusts nobody.
Return one valid order for completing all courses.
Infer a valid character order from a sorted alien dictionary.