Graph AlgosAlgorithmaka post-order topological sort, reverse finish order

DFS Topological Sort

Run DFS, record vertices as they finish, and reverse that list; a grey-to-grey edge during the search means a cycle.

▶ VisualizePattern: Depth-First SearchPractice (2)
Progress

Overview

The DFS approach to Topological Sort exploits a property of depth-first search on a DAG: a vertex finishes (its recursive call returns) only after every vertex reachable from it has finished. Therefore the list of vertices in finish order has every edge pointing *backwards*, and reversing it gives a topological order.

Cycle detection is folded into the same search with three colours: white (unvisited), grey (on the current recursion path), black (finished). Meeting a grey neighbour means the DFS found an edge back to an ancestor on the current path — a directed cycle — and no topological order exists.

The output is the order most DAG algorithms want as a by-product: reversed post-order is also the first half of Kosaraju's Algorithm and the backbone of DP on DAGs.

topological sortDFSpost-orderthree colourscycle detectionO(V + E)

Intuition

A mental model before the formal terms.

You are assembling furniture from a manual that says "attach A only after B and C are done". Start with any piece: before writing it on the to-do list, dive into its dependencies and write those down first, recursively. Each piece gets written only when everything it needs is already written. Now you have a list where dependencies come *before* dependents — except that the DFS wrote things in finish order, which is dependents-last. Reverse it and read from the top.

The grey marker is a "currently working on it" sticky note. If, while resolving a piece's dependencies, you run into a piece that still has its sticky note on, you have gone in a circle.

Example: edges 0→1, 0→2, 1→3, 2→3. DFS from 0: enter 0, enter 1, enter 3, 3 finishes → post [3]; 1 finishes → [3, 1]; enter 2, 3 is black, 2 finishes → [3, 1, 2]; 0 finishes → [3, 1, 2, 0]. Reverse: [0, 2, 1, 3] — every edge points right.

How it works

  1. Colour all vertices white. Prepare an empty list post.
  2. For every white vertex s, call dfs(s).
  3. dfs(u): colour u grey. For each v in adj[u]: if v is grey, a cycle exists — abort; if v is white, dfs(v). After all neighbours, colour u black and append u to post.
  4. Return reverse(post). Alternatively, prepend to a linked list or fill an array from the back to avoid the reverse.
  5. Iterative version: push (u, nextNeighbourIndex) frames on an explicit stack; on exhausting a frame's neighbours, colour black and append. Needed in Python/JavaScript for deep graphs.

Why it works

Consider any edge u → v in a DAG. When DFS scans this edge from u, v is either white (then dfs(v) runs to completion inside dfs(u), so v finishes first), or black (already finished, so again before u). v cannot be grey: grey means v is an ancestor of u on the current path, so a path v ⇝ u exists, and with u → v that is a cycle. Hence in a DAG finish(v) < finish(u) for every edge, and reversed finish order is topological.

Cycle detection is complete: if there is a cycle, the first vertex of the cycle that DFS discovers eventually scans the cycle edge leading to it while it is still grey (every other cycle vertex is reached inside its call).

Every vertex is coloured grey once and black once, every adjacency list is scanned once: O(V + E).

Recognition

How to tell a problem wants this.

  • You need a topological order and are already writing a DFS for something else.
  • The problem is naturally recursive: "to resolve X first resolve everything X depends on" (module loading, build graphs, symbol resolution).
  • You also need to *find* a cycle, not just detect it — the grey vertices on the stack between the two ends of the back edge are the cycle.
“connected groups” → Depth-First Search“prerequisites” → Topological Sort

Interactive visualization

Play, step, change the input. ← → and space work too.

shirttiejacketpantsbeltshoessocks
Recursion path
empty
Post-order (push as finished)
empty
1/19DFS post-order lists each node only after all of its descendants. Reversing that list therefore puts every node before the nodes it points to.
Current nodeOn recursion pathFinished (label = post-order position)DFS tree edge
PseudocodeLearn DFS Topological Sort →
1visited = {}; post = []
2def dfs(u):
3  visited.add(u)
4  for v in neighbors(u):
5    if v not in visited: dfs(v)
6  post.append(u)   # u finishes after all descendants
7for u in nodes: if u not in visited: dfs(u)
8return reversed(post)
Complexity
best O(V + E)
avg O(V + E)
worst O(V + E)
space O(V)
Speed

Pseudocode

1color[*] = WHITE; post = []
2dfs(u):
3  color[u] = GRAY
4  for v in adj[u]:
5    if color[v] == GRAY: cycle -> fail
6    if color[v] == WHITE: dfs(v)
7  color[u] = BLACK; post.append(u)
8for s in 0..n-1: if color[s] == WHITE: dfs(s)
9return reverse(post)

Implementations

1def dfs_topo_sort(out: list[list[int]]) -> list[int]:
2    """DFS topological sort: a vertex is emitted only after every vertex it
3    can reach has been emitted, so pushing on *finish* and reversing gives a
4    valid order. Iterative, because recursion depth is O(V). Returns [] when
5    the graph has a cycle."""
6    n = len(out)
7 
81 · Three colours: 0 = unvisited, 1 = on the current path, 2 = finished
9    state = [0] * n
10    order: list[int] = []
11 
12    for s in range(n):
13        if state[s] != 0:
14            continue
15 
162 · Each frame is [vertex, index of the next neighbour to explore]
17        stack = [[s, 0]]
18        state[s] = 1
19        while stack:
20            frame = stack[-1]
21            u, i = frame[0], frame[1]
22            if i < len(out[u]):
23                frame[1] += 1
24                v = out[u][i]
253 · An edge into a state-1 vertex is a back edge: cyclic
26                if state[v] == 1:
27                    return []
28                if state[v] == 0:
29                    state[v] = 1
30                    stack.append([v, 0])
31            else:
324 · All successors done, so u may now be emitted (post-order)
33                state[u] = 2
34                order.append(u)
35                stack.pop()
36 
375 · Post-order is reverse topological order
38    return order[::-1]
Walkthrough
  1. Frames are two-element *lists* rather than tuples, because frame[1] += 1 must mutate the entry already on the stack.
  2. u, i = frame[0], frame[1] unpacks the frame for readability; the increment then writes back through frame[1] += 1.
  3. Vertices are appended on finish, and order[::-1] reverses at the end to produce topological order.
  4. The state-1 back-edge test returns [] immediately on a cycle.
  5. The iterative form avoids RecursionError, which CPython raises near 1000 frames — reachable on a path graph of a few thousand vertices.
Complexity (this implementation)
time O(V + E) · space O(V)
Language notes
  • A tuple frame is immutable, so frame[1] += 1 raises TypeError; a list (or a small mutable class) is required.
  • sys.setrecursionlimit can raise the recursion cap but risks a genuine C-stack segfault — the explicit stack is the safe answer.
  • order[::-1] returns a new list; order.reverse() reverses in place and returns None, which is a classic source of accidental None returns.
  • graphlib.TopologicalSorter is the standard-library alternative and uses the Kahn-style approach, raising CycleError.
Common mistakes in this language
  • Using a tuple for the frame and hitting TypeError on the cursor increment.
  • Writing return order.reverse(), which returns None because list.reverse mutates in place.
  • Writing the recursive version and hitting RecursionError on a deep graph.
Language differences that matter here
  • Mutating the DFS frame cursor needs a different mechanism in each language: a C++ structured binding to a reference, a JavaScript/TypeScript object (references by nature), and a Python *list* — a tuple would raise.
  • Recursion limits are why all four use an explicit stack, but the failure differs: CPython raises RecursionError near 1000 frames, JS engines throw RangeError near 10000, and C++ overflows the stack with no diagnostic at all.
  • Signalling a cycle: TypeScript can return null and force the caller to handle it; C++, JavaScript and Python return an empty container that collides with the empty-graph case unless the caller checks separately.
  • Reversal: C++ std::reverse and JS/TS Array.prototype.reverse mutate in place and are chainable; Python list.reverse() returns None, so the slice [::-1] is the expression form.

Complexity

Best
O(V + E)
Average
O(V + E)
Worst
O(V + E)
Space
O(V)

Recursion depth up to V; use the iterative variant for long chains.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • You want a topological order from code you are already writing as a DFS.
  • You need to report the actual cycle (grey path segment) rather than just its existence.
  • The reverse post-order itself is needed — e.g. as the first pass of Kosaraju's Algorithm or to evaluate a DAG DP.
Avoid it when
  • Lexicographically smallest order is required — use Kahn's Algorithm with a heap; DFS order depends on adjacency order in a non-obvious way.
  • Level / round counting for parallel scheduling — Kahn's BFS layers give that directly.
  • Extremely deep graphs in Python/JavaScript without converting to the iterative form.

Alternatives

Kahn's AlgorithmTopological Sort

Common mistakes

  • Using only two states (visited / not) — then a cross edge to an already-finished vertex is misreported as a cycle. Grey vs black is the whole point.
  • Appending on entry (pre-order) instead of on exit and reversing — pre-order is not a topological order (e.g. 0→2, 0→1, 1→2 gives pre-order 0,2,1).
  • Forgetting to reverse post, returning dependents before dependencies.
  • Not restarting DFS from every white vertex, so disconnected parts of the DAG are missing from the order.

Interview patterns

  • Course Schedule: return false on a grey neighbour; return the reversed post-order for Schedule II.
  • Longest path in a DAG: relax edges in topological order, or memoise best(u) = 1 + max(best(v)) — the memoised DFS *is* this algorithm.
  • Find Eventual Safe States: vertices that finish black without touching a grey vertex are safe.
Interview questions on this
Mock interviews

Example problems

Course SchedulemediumAlien Dictionaryhard