← Topo Sort · guided lesson
Topological Sort
the story
Topological sort with Kahn's algorithm
Every tool here exists because something was too slow or broke without it. Here is what.
In the late 1950s, big projects such as the US Navy's Polaris missile programme were planned as PERT networks: thousands of events, each waiting for others. Before a computer could analyse such a network, the events had to be listed so that every event came after the ones it waits for. In 1962 A. B. Kahn published "Topological sorting of large networks" in Communications of the ACM. He estimated that, on an IBM 7090, a 30,000-activity PERT network could be ordered in under an hour of machine time — though, as he noted, the method had not yet been programmed.
the problem it solved
Putting thousands of dependent events in a valid order — and noticing when the dependencies loop.
why it matters: without it
Builds, spreadsheets and schedulers would have to guess an order and retry, and a circular dependency would hang instead of failing with a clear error.
sources: Kahn — Topological sorting of large networks (CACM, 1962) ↗ · Malcolm, Roseboom, Clark & Fazar — Application of a Technique for Research and Development Program Evaluation (Operations Research, 1959) ↗ · Knuth — The Art of Computer Programming, Vol. 1, §2.2.3 (topological sorting) ↗
also in this chapter: Topological order by DFS (reverse post-order) · Critical path (DP on a DAG) · Tree centre by peeling leaves
the idea
The idea in 30 seconds
Draw an arrow u → v for "u must happen before v". A topological order lists every vertex so all arrows point forward.
Kahn: repeatedly take a vertex with no arrows coming in (nothing left to wait for). DFS: a vertex is finished only after everything it points to — so reverse the finish order.
It exists only if there is no directed cycle. Both methods detect the cycle for free — that is half of all interview questions on this topic.
picture this
A Gradle or Maven build: a module compiles only after the modules it depends on. The build tool keeps picking a module whose dependencies are already built, builds it, and repeats. If module A needs B and B needs A, nothing can ever start — the build stops with a cycle error.
watch it
Kahn's algorithm — in-degree array + queue
Predict mode is on. Before each step, guess what happens, then watch. Wrong guesses are fine; that is how it sinks in.
Kahn's algorithm — in-degree array + queue
Numbers under each vertex are in-degrees. A vertex turns violet when it reaches 0 and joins the queue; lime when output.
On this screen ← / → step the simulation. Use the buttons below to move through the lesson.
watch it
DFS — colours, call stack and the finished stack
Predict mode is on. Before each step, guess what happens, then watch. Wrong guesses are fine; that is how it sinks in.
DFS — colours, call stack and the finished stack
Amber = on the current path (gray). A vertex is pushed only once everything it points to is finished. Pop the stack to read the order.
On this screen ← / → step the simulation. Use the buttons below to move through the lesson.
key idea 1 of 8
Read it once. Say it out loud once. Bas.
A DAG (directed acyclic graph) always has at least one topological order; a graph with a directed cycle has none.
key idea 2 of 8
Read it once. Say it out loud once. Bas.
Kahn's algorithm (BFS): compute in-degrees, queue every in-degree-0 vertex, pop → output → decrement neighbours → enqueue new zeros. O(V + E).
key idea 3 of 8
Read it once. Say it out loud once. Bas.
Cycle check with Kahn: if fewer than V vertices were output, the rest are stuck on (or behind) a cycle.
key idea 4 of 8
Read it once. Say it out loud once. Bas.
DFS method: three colours — white (unvisited), gray (on the current path), black (finished). Push a vertex when it turns black; the reversed push order is a topological order.
key idea 5 of 8
Read it once. Say it out loud once. Bas.
Cycle check with DFS: an edge into a gray vertex is a back edge = a cycle. An edge into a black vertex is harmless.
key idea 6 of 8
Read it once. Say it out loud once. Bas.
Orders are usually not unique. Need the lexicographically smallest one? Swap Kahn's queue for a PriorityQueue → O(V log V + E). Unique order ⇔ Kahn's queue never holds 2+ vertices.
key idea 7 of 8
Read it once. Say it out loud once. Bas.
Process vertices in topological order and you can do DP on a DAG: longest path / critical path in O(V + E) — NP-hard on general graphs, easy on DAGs.
key idea 8 of 8
Read it once. Say it out loud once. Bas.
Watch the edge direction in the input: LeetCode's [course, pre] means the arrow goes pre → course.
spot the pattern
When you see this, think this
"prerequisites", "depends on", "must happen before", "build order"
Directed graph + topological sort
"Is it possible to finish / schedule everything?"
Cycle detection: Kahn count or DFS gray back edge
Derive an ordering from sorted examples (alien dictionary)
Compare adjacent items, first difference = an edge, then topo sort
"Minimum time when tasks run in parallel"
Longest path in a DAG (Kahn + DP)
+3 more signals on the chapter page
watch out
A trap or two
Many wrong answers in interviews come from small slips like these, not from the hard part.
- Reversing edge direction:
[course, pre]means pre → course. Draw one edge on paper before coding. - Using a two-state
visited[]for directed cycle detection — a diamond (two paths into one vertex) looks like a cycle. You need gray vs black.
quick check
One question. No pressure.
Kahn's algorithm finished and output 5 of 7 vertices. What does that mean?
now try
Your first real problem
You know enough to try this one. Stuck? Use the hints; that is what they are for.
Course Schedule
open the problem →recall
Flip a few cards
Answer in your head first, then flip. Grade yourself honestly; the schedule brings back what you forget.
When does a topological order exist?
Question 1: When does a topological order exist?
done
Lesson complete
Chalo, that is the core. The full chapter has the rest: cost tables, Java details and more problems.