Topological Sort with DFS: Ordering a DAG in Post-Order
Learn topological sort with DFS — order a DAG so every edge points forward, using post-order finish times, a worked walkthrough, JavaScript code, and complexity.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Some things can only happen in an order. You cannot compile a file before its imports, take a course before its prerequisite, or build a wall before pouring the foundation. Model those "must come first" rules as arrows in a directed graph and the question becomes: is there a single line that respects every arrow at once?
That linear ordering is a topological sort, and depth-first search produces one almost for free. The trick is not when DFS visits a node, but when it finishes one — the moment every dependency downstream has been fully explored.
Master this and a whole class of scheduling, build-order, and dependency problems collapses into the same six-line pattern.
The problem
Given a directed acyclic graph (a DAG) with n nodes numbered 0..n-1 and an adjacency list graph where graph[u] lists the nodes u points to, return any ordering of all nodes such that for every edge u -> v, node u appears before v.
A DAG can have several valid orderings. You return one. If the graph contains a cycle, no ordering exists — the dependencies contradict each other.
Input: n = 4, graph = [[1, 2], [], [3], []]
// edges: 0->1, 0->2, 2->3
Output: [0, 2, 3, 1]
// 0 comes before 1 and 2; 2 comes before 3.
// Every arrow points "forward" in the list.[0, 1, 2, 3] is also valid here. Both satisfy all three edges; the problem only asks for one legal line.
The brute force baseline
The literal definition suggests brute force: try every possible ordering and keep the first one where no edge points backward.
function topoBrute(n, graph) {
const perms = permutations([...Array(n).keys()]);
for (const order of perms) {
const pos = new Map(order.map((node, i) => [node, i]));
const ok = graph.every((nbrs, u) =>
nbrs.every((v) => pos.get(u) < pos.get(v))
);
if (ok) return order;
}
return []; // no valid ordering (cycle)
}This is correct but hopeless. There are n! permutations, and checking each one scans all E edges, giving O(n! · E). At n = 12 that is already half a billion orderings. The definition is a specification, not an algorithm — you never actually need to enumerate orderings.
The key insight: record nodes by finish time
Here is the reframe. In DFS, a node is finished only after every node reachable from it has been finished first. So if you append each node to a list at the moment it finishes, the deepest dependencies land in the list before the nodes that depend on them.
That gives you the reverse of what you want: dependents accumulate after their dependencies. Flip the list and every edge now points forward. That is the entire algorithm — no incoming-edge counting, no repeated scans.
Concretely: run DFS, and after a node's loop over its neighbors completes (post-order), push it onto a stack. When traversal ends, reverse the stack. This is why it is called post-order DFS topological sort: the work happens on the way out of each recursive call, not on the way in.
The optimal solution
This mirrors the exact code the visualizer steps through, variable names and all.
function topologicalSortDFS(n, graph) {
let ans = [];
let visited = new Set();
function dfs(curr) {
visited.add(curr);
for (let neighbor of graph[curr]) {
if (!visited.has(neighbor)) {
dfs(neighbor);
}
}
ans.push(curr); // post-order: push AFTER all descendants
}
for (let i = 0; i < n; i++) {
if (!visited.has(i)) {
dfs(i);
}
}
return ans.reverse();
}Two structural details carry the whole thing:
ans.push(curr)sits after the neighbor loop, not before. Push before and you would record pre-order (the order you enter nodes), which does not respect dependencies.- The outer
forloop restarts DFS on any node not yet visited. A DAG can be several disconnected pieces, and every node must appear in the output — one DFS from node 0 might not reach all of them.
Walkthrough
Trace n = 4, graph = [[1, 2], [], [3], []]. The ans column is the post-order stack as it grows; curr is the node the active dfs call is working on.
| Step | Call | curr | visited | ans (finish order) |
|---|---|---|---|---|
| 1 | dfs(0) | 0 | {0} | [] |
| 2 | 0 → neighbor 1, dfs(1) | 1 | {0,1} | [] |
| 3 | 1 has no neighbors → finish 1 | 1 | {0,1} | [1] |
| 4 | back in 0 → neighbor 2, dfs(2) | 2 | {0,1,2} | [1] |
| 5 | 2 → neighbor 3, dfs(3) | 3 | {0,1,2,3} | [1] |
| 6 | 3 has no neighbors → finish 3 | 3 | {0,1,2,3} | [1,3] |
| 7 | back in 2, loop done → finish 2 | 2 | {0,1,2,3} | [1,3,2] |
| 8 | back in 0, loop done → finish 0 | 0 | {0,1,2,3} | [1,3,2,0] |
| 9 | outer loop: 1,2,3 all visited → reverse() | — | — | [0,2,3,1] |
Notice node 1 finishes first even though 0 started first — 1 is a dead end with no dependents, so it is safe to place it last. Reversing [1,3,2,0] puts 0 at the front and 1 at the back, exactly where the edges demand. That inversion is the crux: first to finish = last in the order.
Complexity
| Approach | Time | Space | Why |
|---|---|---|---|
| Brute force (permutations) | O(n! · E) | O(n) | tries every ordering, validates each against all edges |
| DFS post-order | O(V + E) | O(V + E) | each node and edge visited once; recursion + visited set + output |
The DFS version touches every node once (guarded by the visited set) and walks every edge once inside the neighbor loops — the textbook O(V + E) of a graph traversal. Space is the recursion call stack (up to O(V) deep), the visited set (O(V)), and the ans list (O(V)), plus the O(E) adjacency list itself.
Common mistakes
- Pushing pre-order instead of post-order. Moving
ans.push(curr)above the neighbor loop records entry order, which does not honor dependencies. The push must come after the loop. - Forgetting the final reverse. Post-order gives dependencies-first in reverse. Skip
reverse()and your output has every edge pointing backward. - Only starting DFS from one node. Without the outer
forloop, disconnected components never get visited and vanish from the output. Every unvisited node needs its own DFS launch. - Assuming a plain
visitedset detects cycles. It does not. A singlevisitedflag cannot tell "already finished" apart from "currently on the path above me." To detect cycles you need a second state — avisitingset for nodes on the active recursion path. Revisiting a node that is stillvisitingmeans a back edge, and topological sort is impossible. The interactive visualizer highlights exactly this three-state coloring. - Recursing on a graph too deep for the call stack. Millions of chained nodes can overflow the native recursion limit; rewrite DFS with an explicit stack when depth is a risk.
Where this pattern shows up next
Post-order DFS and its BFS cousin power a large family of graph-ordering problems:
- Breadth First Search (BFS) — the level-by-level traversal behind Kahn's algorithm, the queue-based alternative to DFS topological sort.
- Reconstruct Itinerary — a Hierholzer-style post-order DFS that appends airports on the way out, the same "finish then push" move used here.
- Word Ladder — shortest transformation as a BFS over an implicit graph, a good contrast for when ordering versus distance matters.
- Swim in Rising Water — grid search where ordering by threshold, not by depth, decides the traversal.
To watch the recursion stack and the topological result stack fill in real time, step through the Topological Sort DFS visualizer on a diamond DAG and a cyclic graph side by side.
FAQ
Why does DFS give a topological order for free?
Because a node finishes only after everything reachable from it has finished. If you append each node the instant its DFS call returns, dependencies land in the list before their dependents — just in reverse. Reversing that finish-order list yields a valid topological sort. No incoming-edge bookkeeping is needed; the recursion's natural post-order does the ordering.
What is the time complexity of topological sort using DFS?
O(V + E), where V is the number of nodes and E the number of edges. The visited set guarantees each node is entered by DFS exactly once, and each edge is examined once inside the neighbor loops. Space is O(V + E): O(V) for the recursion stack, visited set, and output list, plus O(E) for the adjacency list.
How do I detect a cycle during DFS topological sort?
Track a second set — call it visiting — holding the nodes on the current recursion path. Add a node to visiting when you enter it and remove it when it finishes. If DFS reaches a node already in visiting, that is a back edge, meaning a cycle, so no topological order exists. A plain visited set alone cannot distinguish a finished node from one still on the active path.
Should I use DFS or Kahn's BFS algorithm for topological sort?
Both run in O(V + E) and produce a valid ordering. DFS is compact and recursive, and it detects cycles via the visiting set. Kahn's algorithm processes nodes with zero remaining in-degree in a queue, which avoids recursion depth limits and naturally surfaces a cycle when the queue empties before all nodes are output. Choose Kahn's when you want iteration and explicit in-degree tracking; choose DFS when you prefer the shorter post-order formulation.
Why is the output reversed at the end?
Post-order DFS pushes a node only after all of its descendants are already on the list, so the list ends up ordered dependents-before-dependencies — the opposite of what you want. Reversing it once at the end flips every edge to point forward. An equivalent trick is to push finished nodes onto a stack and pop them, which reads the finish order back-to-front automatically.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.