Topological sort — order under dependencies
Start with the everyday version, no code yet. You have a pile of tasks, and some tasks can't begin until other tasks are done first. Lay them out in a single line so that every task comes after all the tasks it depends on. That line is a topological order, and finding one is called a topological sort ("topo sort" for short).
Concrete examples you already do without thinking: you must register before you can attend a course; you must compile a library before the program that links against it; you must boil water before you steep the tea. A topological sort is simply the discipline of writing the whole to-do list out in an order where nothing ever asks you to do something before its prerequisite.
Two facts to hold onto from the start. First, the order is usually not unique — if two tasks don't depend on each other, either can go first, so there can be many valid orders. Second, an order only exists if there are no circular dependencies: if A waits on B and B waits on A, neither can ever be first, and no valid order exists at all. Detecting that impossibility falls out of the algorithm for free.
The vocabulary, defined inline
Topological sort comes with a small cluster of graph terms. Each one is plain once you have the picture, so here they are defined as we go:
- Directed graph — a set of nodes (also called vertices: the things, e.g. tasks or courses) joined by edges that are one-way arrows. "Directed" means each arrow has a direction; an arrow from b to a is not the same as one from a to b.
- Dependency — the relationship an arrow encodes. We draw an arrow from b to a to mean "b must come before a" — a depends on b. (Watch the direction carefully; problems phrase it both ways.)
- Cycle — a path of arrows that loops back to where it started (a→b→c→a). A cycle is a circular dependency: each task waits on the next, forever.
- DAG — a Directed Acyclic Graph: a directed graph with no cycles. "Acyclic" just means "contains no cycle." This is the only kind of graph that has a topological order — which is why topo sort is defined only on DAGs.
- Topological order — a linear arrangement of all the nodes such that for every arrow b→a, b appears somewhere before a. Equivalently: every node comes after all of its prerequisites.
- Indegree — for a single node, the number of arrows pointing into it. Read it as "how many unmet prerequisites this node still has." A node with indegree 0 has nothing left blocking it and is ready to go.
- Kahn's algorithm — the BFS-style (breadth-first) approach below: repeatedly take any indegree-0 node, remove it, and decrement the indegrees of whatever it pointed to. (BFS = breadth-first search, the strategy of processing things in waves using a queue.)
- DFS-based topo sort — the alternative recursive approach (depth-first search): explore as deep as you can, and prepend each node to the answer as its exploration finishes. Both produce a valid order; this lesson focuses on Kahn's.
- Cycle detection — the act of discovering that no valid order exists. With Kahn's it is automatic: a cycle means some nodes can never reach indegree 0, so they never get taken.
📖 Walk me through it — plain English
A topological sort is just an ordering of tasks that respects their dependencies: if task A must come before task B, then A appears earlier in the line. We model this as a directed graph — a set of nodes (the tasks) connected by one-way arrows (the dependencies). An arrow from b to a means "do b before a". The classic phrasing is the Course Schedule problem: courses are nodes, a prerequisite pair [a, b] means "you must take b before a", and we ask: can you finish every course? (i.e. is there a valid order at all?)
The trick we use is Kahn's algorithm. The key idea is indegree — for each node, count how many arrows point into it, i.e. how many prerequisites it still has unmet. A node with indegree 0 has nothing blocking it, so we can take it right now. Once we take it, we "remove" its outgoing arrows, which lowers the indegree of everything it pointed to. Some of those may now hit 0 and become takeable. We keep doing this until nothing is left.
Analogy: think of getting dressed. You can't put on shoes before socks. So you start with whatever has no prerequisite (underwear, socks), put those on, and that "unlocks" the next layer (pants, shoes). You always grab whatever currently has nothing blocking it. If you ever get stuck with items remaining but none unlocked — say a glove that requires a ring that requires that same glove — that's a cycle, and no valid order exists.
Let's trace n = 4 courses with prereqs [[1,0], [2,0], [3,1], [3,2]]. Reading each pair as [a, b] = "b before a", the arrows are 0→1, 0→2, 1→3, 2→3. The cells below show the indegree array (index 0,1,2,3). We use a queue (a line where we add to the back and remove from the front) to hold ready nodes, and a counter taken.
Final check: taken == n → 4 == 4 → true, so all courses can be finished. The order we popped them, 0 → 1 → 2 → 3, is one valid topological order.
Why it works: a node only enters the queue once its indegree reaches 0, meaning every prerequisite has already been popped before it — so the pop order always respects dependencies. And here's the free bonus: if the graph had a cycle (A needs B and B needs A), those nodes can never reach indegree 0, so they never get popped. taken would end below n and we'd return false — instant cycle detection. The cost is O(n + e) where n is the number of nodes and e the number of edges (arrows): we touch each node once when we pop it and walk each arrow exactly once when lowering an indegree.
Kahn's algorithm: BFS from indegree-0 nodes. As a bonus you get free cycle detection — anything left with indegree > 0 is in a cycle.
A second trace: how a cycle gets caught
The walkthrough above showed a clean DAG that fully sorts. To make cycle detection concrete, run the same machine on a graph that cannot be ordered. Take n = 3 with prereqs [[1,0], [2,1], [0,2]]. Reading each pair as [a, b] = "b before a", the arrows are 0→1, 1→2, 2→0 — a loop. Each node has exactly one arrow pointing into it, so the starting indegree array is [1, 1, 1].
- Seed the queue: scan for any node with indegree 0. There are none — every node has indegree 1. So the queue starts empty and
taken = 0. - Main loop: the
while qloop never even begins, because the queue is empty from the start. Nothing is popped, no indegree is ever decremented. - Final check:
taken == n→0 == 3→ false. The three nodes are stuck waiting on each other in a ring; none could ever be "first," so no valid order exists.
This is the whole story of cycle detection: leftover nodes are the cycle. If at the end taken < n, the n - taken nodes that were never popped are exactly the ones tangled in (or downstream of) a circular dependency. You don't need a separate check — the counter already told you.
Recognition signals — when to reach for topo sort
In an interview or a real system, these phrasings are the tell that a topological sort is the tool:
"Can this all be done?"
Course Schedule: given courses and prerequisite pairs, is there any order that finishes them all? This is a pure cycle-detection question — return taken == n.
"In what order?"
Build systems and task schedulers: compile modules so each dependency is built first; resolve package install order. Collect the pop sequence as the answer.
"Respect prerequisites / dependencies"
Anytime the input is a list of "X must come before Y" constraints over a finite set of items, you have a directed graph and you want its topological order.
Spreadsheets & pipelines
Recompute cells so each formula runs after the cells it reads; order stages of a data pipeline. Same shape, different costume.
Pitfalls to watch for
- Cycles are the silent failure. If the graph has a cycle there is no valid order. Always finish with the
taken == ncheck (or "is the output length n?"). Forgetting it means you happily return a partial, wrong order on cyclic input. - The order is not unique. When several nodes sit at indegree 0 at once, any of them may go next, so two correct programs can print different orders. Don't assume a single "right" answer — graders accept any valid topological order. (Using a min-heap instead of a plain queue gives the lexicographically smallest order if a problem demands a specific tie-break.)
- Edge direction is easy to flip. The pair
[a, b]in Course Schedule means "take b before a," so the arrow goes b→a and it isa's indegree that increases. Reverse this by accident and you solve the mirror-image problem. Re-read the problem's exact wording before building the graph. - Indegree, not outdegree. Kahn's seeds and decrements indegree (arrows coming in). Counting outgoing arrows instead is a common slip.
- Don't enqueue a node twice. A node should join the queue only at the moment its indegree hits exactly 0 (
if indeg[v] == 0, not<= 0). The strict equality guarantees each node is enqueued and counted once.
from collections import defaultdict, deque
def can_finish(n, prereqs):
g = defaultdict(list); indeg = [0] * n
for a, b in prereqs:
g[b].append(a); indeg[a] += 1
q = deque([i for i in range(n) if indeg[i] == 0])
taken = 0
while q:
u = q.popleft(); taken += 1
for v in g[u]:
indeg[v] -= 1
if indeg[v] == 0: q.append(v)
return taken == nfunction canFinish(n:number, prereqs:number[][]): boolean {
const g: number[][] = Array.from({length:n}, ()=>[]);
const indeg = new Array(n).fill(0);
for (const [a,b] of prereqs) { g[b].push(a); indeg[a]++; }
const q:number[] = [];
for (let i=0;i<n;i++) if (indeg[i]===0) q.push(i);
let taken = 0;
while (q.length) {
const u = q.shift()!; taken++;
for (const v of g[u]) if (--indeg[v]===0) q.push(v);
}
return taken === n;
}From "can it?" to "what order?": the template returns a yes/no. To emit the actual order, keep an order list and append u each time you pop it (right where taken increments). At the end, if len(order) == n return order, otherwise return [] to signal a cycle. The pop sequence is itself a valid topological order — no sorting needed.
Go deeper (optional): the recursive alternative, DFS-based topo sort, runs depth-first from each unvisited node and prepends a node to the answer once all of its descendants are finished (a "post-order" emission, then reversed). It detects cycles with a three-color/visiting-set marking that catches a back-edge into a node still on the recursion stack. Same O(n + e) cost and same valid-order guarantee — Kahn's is usually easier to reason about under interview pressure because the cycle check is just a counter.
Takeaway: a topological sort linearizes a DAG so every node follows its prerequisites. Build an indegree count, seed a queue with all indegree-0 nodes, and repeatedly pop a node and decrement the indegrees of its successors, enqueuing each as it hits 0 (Kahn's algorithm). The pop order is a valid topological order; if fewer than n nodes ever pop, the leftovers form a cycle and no order exists. Cost is O(n + e). Watch the edge direction, remember the order isn't unique, and never skip the final taken == n check.
Return a topological order with Kahn's algorithm — or an empty array if a cycle exists: