Skip to content

level 7 · Graphs

Topological Sort

Put jobs in an order where nothing happens before what it depends on.

10 min 90 XP

what is it

Start here

Some things must happen before others. You can't put your shoes on before your socks. You can't take the advanced course before the intro. A topological sort finds an order that respects every one of those rules at once.

The graph here is *directed*: an arrow from A to B means 'A must come before B'. The trick is to count, for each job, how many arrows point *into* it — how many things still block it. That count is called the in-degree.

Anything with an in-degree of zero is blocked by nothing, so it can go right now. Do it, then cross it off — which reduces the in-degree of everything it was blocking. Some of those may now hit zero themselves, and they join the queue. Repeat.

And here's the beautiful part: if you ever run out of unblocked jobs while work remains, the dependencies must contain a **cycle** — A waits on B, which waits on A. There is no valid order, and the algorithm has just proved it. That's why 'Course Schedule' on LeetCode is really just a cycle check in disguise.

real-life analogy

Picture it

Getting dressed

Underwear before trousers. Trousers before belt and shoes. Socks before shoes. Shirt before jacket. There isn't one single correct order — you could do socks first or shirt first — but there are plenty of wrong ones. A topological sort finds any of the valid ones.

interactive visualization

Watch it run

The number on each node is how many jobs still block it — its in-degree.

socks 0
underwear 0
shirt 0
trousers 1
belt 2
shoes 2
jacket 2

queue · FIFO

empty

take from the front

Getting dressed: some things must come before others. The arrow under → trousers means underwear goes on first. The number on each node counts how many things still block it — its in-degree.

step 01/17

  • just discovered
  • visited
  • found it
  • waiting in the queue / stack
1function topoSort(graph) {
2 const indegree = {};
3 for (const v of graph.nodes) indegree[v] = 0;
4 for (const [u, v] of graph.edges) indegree[v]++;
5
6 // everything that depends on nothing can start now
7 const ready = graph.nodes.filter(v => indegree[v] === 0);
8 const order = [];
9
10 while (ready.length > 0) {
11 const u = ready.shift();
12 order.push(u);
13
14 for (const v of graph.next[u]) {
15 indegree[v]--;
16 if (indegree[v] === 0) ready.push(v);
17 }
18 }
19
20 if (order.length < graph.nodes.length) return null; // a cycle
21 return order;
22}

variables right now

note
number on each node = jobs still blocking it
comparisons 0moves 0

the dry run · every step, in words

17 steps

complexity

What it costs

best case
O(V + E)
average
O(V + E)
worst case
O(V + E)
extra memory
O(V)

Every job is queued once and every dependency arrow is followed once: V + E. The same cost as BFS or DFS — because underneath, that's exactly what it is.

  • O(1)
  • O(log n)
  • O(n) · this one
  • O(n log n)
  • O(n²)
input size →work →

common mistakes

Common traps

  • Running it on an undirected graph.

    Topological order only means something when edges have direction. 'A before B' is a one-way claim; an undirected edge makes no such claim.

  • Assuming there's one correct answer.

    There are usually many valid orders. Socks-then-shirt and shirt-then-socks are both fine. Any order where every arrow points forwards is correct.

  • Not checking whether every node made it into the order.

    If some are left over, there's a cycle and no valid order exists. That check is not an afterthought — it's how you detect the impossible case.

quiz

Check yourself

Three questions. Get them all right to finish the lesson.

+90 XP

01What does a node's in-degree of zero mean?

02You run out of unblocked jobs but some jobs remain. What does that prove?

03How many valid topological orders does a graph usually have?

practice

Solve it on LeetCode

You've seen it run — now write it yourself. These are real LeetCode problems that use exactly this idea, from gentlest to toughest.