Topological sort (Kahn's algorithm)
Put tasks in an order where every task comes after the tasks it depends on, by repeatedly taking a task that has nothing left to wait for.
O(n + e)Space O(n + e)5 practice problemsStep-through pictureThe idea
Many jobs have rules like "A must happen before B". A build tool must compile a module after the modules it imports. A course plan must put an intro class before the advanced one. An order of tasks that respects every rule is called a topological order.
Kahn's algorithm builds that order the way you would by hand. First, count for each task how many tasks it is still waiting for. This count is called the in-degree. Any task waiting for nothing can go now. When a task is done, every task that was waiting on it has one less thing to wait for, and any whose count drops to 0 can go next.
If the rules contain a loop, such as A before B and B before A, no order exists. Kahn's algorithm notices this for free: the tasks in the loop never reach a count of 0, so the final order has fewer than n tasks.
An everyday example
Getting dressed in the morning
Socks go on before shoes, underwear before pants, and pants before shoes and belt. To get dressed, you pick any item that has nothing left to wait for, like socks or underwear, and put it on. Each item you put on can free up others: once underwear and pants are on, the belt is free. You keep going until everything is on. If someone wrote "shoes before socks" and "socks before shoes", you could never start.
| In the example | In the code |
|---|---|
| An item of clothing | A node from 0 to n - 1 |
| "Socks before shoes" | An edge [from, to] |
| How many items must go on first | indegree[node] |
| Items you can put on right now | Nodes in the queue |
| The order you got dressed | The order array |
From the slow way to topological sort (kahn's algorithm)
- The slowest way to order tasks is to try every order and check each one against the rules:
n!orders, over 3 million for just 10 tasks. A better slow way: repeatedly scan all tasks for one whose requirements are all placed, place it, and scan again. That isnscans of the whole graph, aboutn * (n + e)work. - Most of each scan is wasted. A task can only become ready at one moment: when the last of its requirements is placed. So instead of re-checking every task, keep a count for each task of how many requirements are still unplaced. That count is the in-degree.
- Placing a task lowers the count of each task that waits on it, by following its outgoing edges once. When a count drops to 0, that task just became ready, so put it in a queue of ready tasks. Every edge lowers one count exactly once.
- If the queue runs dry before every task is placed, the tasks left are each waiting on another task that is left, so they wait on each other in a loop. Return an empty order in that case. That loop is Kahn's algorithm.
How it works
- Build
graphwith an edge from each task to the tasks that depend on it, and countindegree[to]for every edge. - Put every node with
indegree0 into thequeue. These can go first. - Take the next
nodefrom the queue and add it toorder. - For each
nextthat depends onnode, lowerindegree[next]by one, because one of its requirements is done. - If
indegree[next]reaches 0, everything it needs is done, so add it to the queue. - When the queue is empty, return
orderif it holds allnnodes. Otherwise there is a cycle: return an empty array.
Watch it run
This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.
See every step at onceThe same run, laid out side by side
The code
Point at a note to light up the lines it explains.
function topoSortKahn(n, edges) {const graph = Array.from({ length: n }, () => []);const indegree = new Array(n).fill(0);for (const [from, to] of edges) {graph[from].push(to);indegree[to]++;}const queue = [];for (let node = 0; node < n; node++) {if (indegree[node] === 0) queue.push(node);}const order = [];for (let head = 0; head < queue.length; head++) {const node = queue[head];order.push(node);for (const next of graph[node]) {indegree[next]--;if (indegree[next] === 0) queue.push(next);}}return order.length === n ? order : [];}
How fast it is
| Time | O(n + e) |
|---|---|
| Extra memory | O(n + e) |
Each node joins the queue once, and each edge lowers one count once. The graph stores every edge, and indegree, queue, and order hold one entry per node.
- Best case
O(n)There are no edges. Every count is 0, every node goes straight into the queue, and no counts are lowered.
- Average case
O(n + e)Each edge is read twice, once to count it and once to lower a count, and each node passes through the queue once.
- Worst case
O(n + e)A dense graph with many edges. The work still grows only with the number of nodes and edges.
Common mistakes
- Pointing edges the wrong way. If
[a, b]means "a needs b", the edge in the graph must go frombtoa. Read the statement carefully. - Forgetting to check
order.length === n. With a cycle you return a partial order that looks fine but is missing tasks. - Starting only from node 0 instead of from every node with in-degree 0.
- Expecting one specific order when several tasks are ready at once. If the problem defines a tie rule, use a heap or sorted list to follow it.
When to use it
Look for these clues in a problem:
- The input has rules like "A must come before B", prerequisites, or dependencies.
- The question asks for a valid order, a build order, or whether finishing everything is possible.
- You need to process things in rounds, where each round is everything that's ready at once.
- A cycle in the rules means the answer is "impossible".
Check yourself
Answer each one in your head first, then open it.
Why does a short order prove there is a cycle?
Every left-over node still waits on another left-over node. Following those waits backward among a limited number of nodes must eventually repeat a node, and that repeat is a cycle.
How many times is each edge looked at?
Twice: once when it is counted into indegree, and once when its from node is placed and the count is lowered.
In the trace, could [4, 2, 1, 0, 3, 5] also be a valid answer?
Yes. 2 and 4 were both ready at the start, so either could go first. Every rule, such as 4 before 1 and 2 before 0, still holds.
In the cycle version of the trace, what does the queue hold when the loop stops?
Nothing. After 0 is placed, 1, 3, and 5 each still have a count of 1, so none of them ever joins the queue.
Practice problems
Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.
0 of 5 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.
Start practicingGo further
You don't need these to start practicing. Open one when you want more.
Why it works
The reasoning that makes it always right
The loop keeps this rule: indegree[x] equals the number of edges into x from nodes not yet in order. At the start nothing is placed, so it is the plain in-degree. Each time a node is placed, the loop lowers the count of every node it points to, which keeps the rule exact.
A node enters the queue only when its count reaches 0, meaning every node that points to it is already in order. So every edge a → b has a placed before b. Counts only go down, so each node reaches 0 at most once and enters the queue at most once, which is why the loop ends.
If order ends shorter than n, every node left over has a count of at least 1, so it waits on another left-over node. Follow those waits backward: there are only so many left-over nodes, so you must eventually repeat one, and that repeat is a cycle. In the other direction, no node on a cycle can ever be first to reach 0. So order.length === n is true exactly when the graph has no cycle.
Going deeper
3 more ideas
Why every task comes after its requirements
A task only enters the queue when its indegree reaches 0, which happens only after every task pointing to it has been taken from the queue and added to order. So each task is added after all of its requirements.
Choosing among ready tasks
When several tasks are ready at once, any of them can go next, so a graph can have many valid orders. If a problem asks for a single specific order, such as "smallest number first", replace the queue with a min-heap or keep the ready tasks sorted. The rest of the algorithm stays the same.
Counting rounds
To find how many rounds a build takes when everything ready can run in parallel, handle the queue one whole level at a time: everything with in-degree 0 is round 1, everything freed by round 1 is round 2, and so on. The number of levels is the length of the longest chain of dependencies.
Work it by hand
Every step in a table, with why
Order 6 build steps, where an edge [a, b] means step a must happen before step b.
n = 6, edges = [[4, 1], [4, 0], [2, 0], [0, 3], [1, 3], [3, 5], [2, 5]]
| Step | node | Counts lowered | indegree | queue waiting | order | Why |
|---|---|---|---|---|---|---|
| 1 | - | - | [2, 1, 0, 2, 0, 2] | [2, 4] | [] | Counting the edges gives each node's in-degree. Only 2 and 4 wait for nothing, so they start in the queue. |
| 2 | 2 | 0: 2→1, 5: 2→1 | [1, 1, 0, 2, 0, 1] | [4] | [2] | 2 is placed. 0 and 5 each lose one requirement but still wait for something. |
| 3 | 4 | 1: 1→0, 0: 1→0 | [0, 0, 0, 2, 0, 1] | [1, 0] | [2, 4] | Both of 4's targets drop to 0 and become ready, in the order graph[4] lists them: 1, then 0. |
| 4 | 1 | 3: 2→1 | [0, 0, 0, 1, 0, 1] | [0] | [2, 4, 1] | 3 still waits for 0. |
| 5 | 0 | 3: 1→0 | [0, 0, 0, 0, 0, 1] | [3] | [2, 4, 1, 0] | 0 was 3's last requirement, so 3 is ready. |
| 6 | 3 | 5: 1→0 | [0, 0, 0, 0, 0, 0] | [5] | [2, 4, 1, 0, 3] | 5 already lost one requirement when 2 was placed. Now its last one is done. |
| 7 | 5 | none | [0, 0, 0, 0, 0, 0] | [] | [2, 4, 1, 0, 3, 5] | 5 has no outgoing edges. The queue is empty and order has all 6 nodes, so it is returned. |
It returns [2, 4, 1, 0, 3, 5]. If you add the edge [5, 1], the loop 1 → 3 → 5 → 1 appears: the run stops at order = [2, 4, 0] with counts [0, 1, 0, 1, 0, 1] left over, and the function returns [].
Compared with other ways
When to pick something else
| Approach | Time | Extra memory | Choose it when |
|---|---|---|---|
| Topological sort (Kahn's algorithm) | O(n + e) | O(n + e) | You want an order without recursion, rounds of parallel work, or a tie rule like smallest-first. |
| Topological sort with DFS | O(n + e) | O(n + e) | You are already doing DFS, or you also need values computed from each node's descendants. |
| Repeated scanning for a ready task | O(n² + n · e) | O(n) | Only for a handful of tasks where the simplest code matters more than speed. |
| Kahn's algorithm with a min-heap | O(n log n + e) | O(n + e) | The problem asks for one specific order, such as the smallest number first among ready tasks. |
Extra memory: O(n + e): the adjacency list holds every edge, and indegree, queue, and order hold one entry per node.
How the steps grow
- Topological sort (Kahn's algorithm), Topological sort with DFS
O(n + e) - Repeated scanning for a ready task
O(n² + n · e) - Kahn's algorithm with a min-heap
O(n log n + e)
| Approach | n = 10 | n = 1,000 | n = 1,000,000 |
|---|---|---|---|
| Topological sort (Kahn's algorithm) | 20 | 2,000 | 2 million |
| Topological sort with DFS | 20 | 2,000 | 2 million |
| Repeated scanning for a ready task | 200 | 2 million | 2 trillion |
| Kahn's algorithm with a min-heap | 43 | 10,966 | 21 million |
Inputs that need care
5 tricky inputs
- No edges:
n = 3, edges = [] - All counts are 0, so the queue starts as
[0, 1, 2]and that is the order. - A self-loop:
[3, 3] indegree[3]is 1, and only placing3itself could lower it. It never reaches 0, so the result is[], which is right: a task can't wait for itself.- The same edge twice:
[[0, 1], [0, 1]] indegree[1]is 2 andgraph[0]lists1twice, so placing0lowers it twice. The order is still correct.- Several separate groups of tasks
- Every node with count 0 is put in the queue at the start, so each group gets started. No outer loop over components is needed.
- Input where
[a, b]means "aneedsb" - Then the edge must go from
btoa. Swap the pair when buildinggraphand counting, or the order comes out backward.
Variations and follow-ups
Twists interviewers add
Smallest-first order
Replace the queue with a min-heap, so among ready tasks the smallest number always goes next. The cost becomes O(n log n + e), and the same input always gives the same single order.
Rounds of parallel work
Handle the queue one batch at a time: everything ready now is round 1, everything those free up is round 2, and so on. The number of rounds is the length of the longest chain of requirements.
Is the order unique?
If the queue ever holds two or more ready nodes at once, they could go in either order, so more than one valid order exists. If it never holds more than one, the order is unique.
Finding the stuck nodes
After a failed run, the nodes with a count above 0 are either on a cycle or wait on one. That list is a good error message, such as "these modules import each other".
In an interview
Spot it, explain it, answer follow-ups
- Spot it from prerequisites, dependencies, build order, or "can all courses be finished?". The last one is a cycle question that Kahn's algorithm answers with
order.length === n. - Explain in-degree in plain words: "for each task, how many things it is still waiting for". Then the algorithm is just "do the tasks waiting for nothing, and update the counts".
- Test by hand: a self-loop, two separate groups, and a three-task loop. Check that the loop case returns
[], not a partial order. - Expect "is the order unique?" (only if the queue never holds two nodes) and "what is the fewest number of rounds?" (process the queue in batches and count them).
Where frontend code uses it
The same idea in real UI code
- Bundlers and build tools such as webpack, Rollup, and Turborepo order modules or packages so each one is handled after its dependencies.
- Package managers decide install and build order for workspaces from the dependency graph in each
package.json. - Spreadsheet-style apps and reactive state libraries recompute cells or derived values in an order where each value comes after the values it reads.