cf.completefrontend
GRAPHS · CORE

Topological sort (DFS)

Order tasks so each comes after its requirements by running DFS and listing each task only after everything it leads to is finished.

Time O(n + e)Space O(n + e)3 practice problemsStep-through picture

The idea

This is a second way to find a topological order: an order of tasks where every edge from → to has from before to. It uses depth-first search instead of in-degree counts.

The key fact: when DFS finishes a node (all of its outgoing edges are fully explored), every node it leads to has already finished. So if you write nodes down in the order they finish, every node appears after the nodes it points to. Reverse that list and every node appears before the nodes it points to, which is a topological order.

To catch cycles, each node has three states: new, in progress (on the current DFS path), and done. Meeting an in-progress node means you walked in a circle back to your own path, so no order exists.

An everyday example

Writing a recipe backwards

To bake a cake you need frosting and a baked sponge; the sponge needs batter; the batter needs eggs and flour. Starting from the cake, you follow each requirement as deep as it goes. You can only write a step down once all of its requirements are written. Reading your notes from bottom to top would give the cake first, so you flip the list over to get the order to actually cook in.

How the example maps to the code
In the exampleIn the code
Following a requirement deeperCalling visit(next)
A step you are still working outstate[node] === 1, in progress
Writing a step down once its needs are writtenorder.push(node) after the loop
Flipping the notes overorder.reverse()

From the slow way to topological sort (dfs)

  1. Suppose you already know DFS and want a dependency order from it. The first idea is to list nodes in the order DFS enters them. That fails: with edges 0 → 1 and 2 → 1, entering from 0 gives [0, 1, 2], and 1 comes before 2 even though 2 must come first.
  2. Look at when DFS finishes a node instead, meaning the moment visit(node) returns. By then, every node it can reach has been visited and has finished too. So if you write nodes down as they finish, each node is written after every node it leads to.
  3. That is backward from what you want, but only backward. Reverse the finish list and each node comes before every node it leads to, which is exactly a topological order. So push a node after its neighbor loop, and reverse order at the end.
  4. Two details finish it. A DFS from one node may not reach everything, so start one from every node. And a cycle must be caught, which needs to tell "on my current path" apart from "finished earlier": three states instead of a visited flag. That is topological sort with DFS.

How it works

  1. Build graph from the edges and set every state to 0 (new).
  2. For each node from 0 to n - 1, call visit(node).
  3. In visit, if the node is in progress (state 1), you found a cycle: return false. If it is done (state 2), return true right away.
  4. Mark the node in progress and visit every neighbor. If any visit finds a cycle, pass the false up.
  5. After all neighbors are finished, mark the node done and push it to order.
  6. At the end, reverse order. Every node now comes before every node it points to.

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.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function topoSortDfs(n, edges) {
  2. const graph = Array.from({ length: n }, () => []);
  3. for (const [from, to] of edges) graph[from].push(to);
  4. const state = new Array(n).fill(0);
  5. const order = [];
  6. function visit(node) {
  7. if (state[node] === 1) return false;
  8. if (state[node] === 2) return true;
  9. state[node] = 1;
  10. for (const next of graph[node]) {
  11. if (!visit(next)) return false;
  12. }
  13. state[node] = 2;
  14. order.push(node);
  15. return true;
  16. }
  17. for (let node = 0; node < n; node++) {
  18. if (!visit(node)) return [];
  19. }
  20. return order.reverse();
  21. }

How fast it is

TimeO(n + e)
Extra memoryO(n + e)

Each node is visited once and each edge is followed once. The graph, state, order, and the call stack together hold O(n + e) entries.

  • Best caseO(n)

    There are no edges. Each outer call marks a node, finds no neighbors, and finishes it.

  • Average caseO(n + e)

    Each node gets one real visit, and each edge causes one call, which may return at once.

  • Worst caseO(n + e)

    Every node and edge is explored, which happens whenever there is no cycle.

Common mistakes

  • Pushing a node to order before visiting its neighbors. That gives a preorder, which is not a valid dependency order.
  • Forgetting to reverse order at the end, so every dependency comes after the thing that needs it.
  • Using a single visited flag. It reports a cycle whenever two paths meet at the same node, even without a loop.
  • Only calling visit from node 0, missing nodes that can't be reached from it.

When to use it

Look for these clues in a problem:

  • You need a dependency order, and you are already doing DFS on the graph.
  • The question also asks for something computed from each node's descendants, such as the longest chain below it.
  • You need to detect a dependency loop at the same time as ordering.
  • The graph is given as an adjacency list and recursion depth is small enough.

Check yourself

Answer each one in your head first, then open it.

Why push a node after its neighbor loop and not before?

After the loop, every node it leads to has already been pushed, so the list has the right shape to reverse. Pushing before gives entering order, which breaks examples like 0 → 1 with 2 → 1.

In the trace, why didn't visit(4) from 1 push 4 a second time?

4 was already in state 2, done, so the call returned true at once. Each node is pushed exactly once.

What does finding a node in state 1 mean?

That node is on the current chain of calls, so there is a path from it to the current node. The edge back to it closes a cycle.

How deep can the recursion go?

Up to n calls, on a single chain like 0 → 1 → 2 → .... Every node on the chain is in progress at the same time.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 3 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

medium

Go 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

Take any edge a → b at the moment visit(a) looks at it, while a is in progress. There are three cases. If b is new, visit(b) runs and finishes completely before a can finish. If b is done, it was pushed already. Either way, b is pushed before a, so after reversing, a comes before b.

The third case is b in progress. The nodes in progress are exactly the current chain of calls, so b is an ancestor of a on the path: there is a path b → ... → a, and with the edge a → b that is a cycle. The code returns false, and no order exists anyway. So when the graph has no cycle, every edge falls into the first two cases and the reversed list is a valid order.

When the graph does have a cycle, it is always caught. Let x be the first node of the cycle to be marked in progress. Every other node on the cycle is still new and reachable from x, so it is visited before x finishes. That includes the node just before x on the cycle, whose edge then finds x in progress. It all ends because each node is marked in progress once and each edge is followed once.

Going deeper

3 more ideas

Why reversed finish order works

Take any edge a → b. If b was visited first, it finished before a even started. If a was visited first, then visit(a) calls visit(b) (or b is already finishing inside it), so b finishes before a. Either way b is pushed before a, and after reversing, a comes before b. The only failure is when b is still in progress, which means there is a cycle.

Why three states, not two

A plain visited flag can't tell "done earlier" from "on my current path". In the example, 3 is reached twice, from 1 and from 2, but that is not a cycle: by the second time, 3 is done. Only reaching a node that is still in progress (an ancestor on the current path) means there is a loop.

Deep graphs

This version uses recursion, so a chain of tens of thousands of nodes can overflow the call stack. For huge graphs, use Kahn's algorithm, which needs no recursion, or write the DFS with an explicit stack.

Work it by hand

Every step in a table, with why

Order 5 tasks, where an edge [a, b] means a must come before b.

n = 5, edges = [[3, 0], [0, 2], [0, 4], [1, 4], [3, 1]]

StepStepnodestateorderWhy
1Outer loop calls visit(0)0[1, 0, 0, 0, 0][]0 is new, so it is marked 1, in progress. Its edges go to 2 and 4.
2visit(2)2[1, 0, 1, 0, 0][]2 is new. It is marked in progress, on the path 0 → 2.
3Finish 22[1, 0, 2, 0, 0][2]2 has no outgoing edges, so it is done first and pushed first.
4visit(4)4[1, 0, 2, 0, 1][2]Back in visit(0), the next edge leads to 4, which is new.
5Finish 44[1, 0, 2, 0, 2][2, 4]4 has no outgoing edges either.
6Finish 00[2, 0, 2, 0, 2][2, 4, 0]Both of 0's targets are done, so 0 is done and pushed after them.
7Outer loop calls visit(1)1[2, 1, 2, 0, 2][2, 4, 0]1 was never reached from 0, so the outer loop starts it.
8visit(4) from 14[2, 1, 2, 0, 2][2, 4, 0]4 is already done (state 2), so it returns true at once. Reaching a done node twice is not a cycle.
9Finish 11[2, 2, 2, 0, 2][2, 4, 0, 1]1 is pushed after 4, the node it points to.
10Outer loop: visit(2)2[2, 2, 2, 0, 2][2, 4, 0, 1]2 is done, so this call returns at once.
11Outer loop calls visit(3)3[2, 2, 2, 1, 2][2, 4, 0, 1]3 is new. Its edges lead to 0 and 1, both already done.
12Finish 33[2, 2, 2, 2, 2][2, 4, 0, 1, 3]3 is pushed last, after every node it leads to. The outer loop's call on 4 returns at once.
13order.reverse()-all 2[3, 1, 0, 4, 2]Reversing the finish order puts every node before the nodes it points to.

It returns [3, 1, 0, 4, 2]. Check each rule: 3 is before 0 and 1, 0 is before 2 and 4, and 1 is before 4. Kahn's algorithm on the same graph gives [3, 0, 1, 2, 4], which is also valid.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Topological sort (DFS)O(n + e)O(n + e)You are already walking the graph with DFS, need values from each node's descendants, or want the cycle itself.
Kahn's algorithmO(n + e)O(n + e)The graph may be very deep, you want rounds of parallel work, or you need a tie rule such as smallest-first.
Trying every orderO(n! · e)O(n)Only to check answers in tests with 8 or fewer nodes.

Extra memory: O(n + e): the adjacency list holds the edges, state and order hold n entries, and the call stack can be n calls deep on a long chain.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Topological sort (DFS) and the other approaches, on a scale where each line up is 10 times more steps.
  • Topological sort (DFS), Kahn's algorithm O(n + e)
  • Trying every order O(n! · e)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Topological sort (DFS)202,0002 million
Kahn's algorithm202,0002 million
Trying every order36 millionmore than a quadrillionmore than a quadrillion

Inputs that need care

5 tricky inputs
No edges: n = 4, edges = []
Nodes finish in the order 0, 1, 2, 3, so the result is [3, 2, 1, 0]. Any order is valid when there are no rules.
A self-loop: [2, 2]
visit(2) marks 2 in progress, follows the edge to itself, finds state 1, and returns false. The result is [].
A cycle that node 0 can't reach
The outer loop reaches it later and the in-progress check catches it then. This is why the loop starts from every node.
A chain of 200,000 tasks
The recursion goes 200,000 calls deep and throws "Maximum call stack size exceeded". Use Kahn's algorithm or an explicit stack for very deep graphs.
A cycle found halfway through
Some nodes are left in state 1 when false comes back. That is fine because the function returns [] at once, but reset state if you reuse it for another search.

Variations and follow-ups

Twists interviewers add

Explicit stack

Store [node, index of next neighbor] pairs on a stack. Look at the top: if it has another neighbor, move to it; if not, pop it and push the node to order. That is the same post-order with no recursion limit.

Longest chain of tasks

Go through the finished order and compute, for each node, 1 plus the longest chain among the nodes it points to. Because those nodes finished first, their values are ready. This gives the critical path of a project.

Reporting the cycle

Keep a stack of the nodes in progress. When an edge reaches a node in state 1, the part of the stack from that node to the top is the cycle, ready to show in an error message.

Building the order without reversing

Fill an array of size n from the end, putting each finished node at the last free position. The result is already in the right order. Avoid unshift, which moves every element each time.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from dependency words, the same as Kahn's algorithm. Pick this version when the problem also needs something from each node's descendants, or when you are already writing a DFS.
  • Say the key fact first: "a node finishes only after everything it leads to, so reversed finish order is a valid order". Then explain the three states.
  • Test by hand: a diamond like 0 → 1, 0 → 2, 1 → 3, 2 → 3 (not a cycle), a self-loop, and a cycle not reachable from node 0.
  • Expect "why not just a visited flag?". In the diamond, 3 is reached twice; only the third state tells "finished earlier" apart from "on my current path".

Where frontend code uses it

The same idea in real UI code
  • ES module loading evaluates a module only after the modules it imports have been evaluated, which follows a depth-first post-order walk of the import graph.
  • Bundlers walk import statements depth-first from an entry file and can emit modules in post-order so dependencies are defined first.
  • Design systems with tokens that reference other tokens (a button color that points to a brand color) resolve the referenced tokens first with a DFS.

Related algorithms