In DFS-based topological sort, why is the answer the reverse of the finishing order, not the visit order?
answer
- think about the moment recursion returns
- children finish before the parent
- preorder can emit a dependent too early
- finishing order lists dependents first
- one list operation fixes the direction
basics
~20 sA node finishes only after every node it points to has finished, so the finishing sequence lists dependents first. Reversing it puts each node ahead of everything it points to; visit order gives no such guarantee.
solid answer
~50 sTake edges to mean "source must come before target". In the recursive traversal, a node is appended to the finished list at the moment its call returns — and its call returns only after it has recursed into every unvisited successor, so all of its successors are already in the list. That makes the finished list exactly backwards: each node sits after everything that must follow it. One reversal turns it into a valid order. Visit order fails because a node can be visited long before an unrelated predecessor is even reached: with edges `X -> Z` and `Y -> Z`, starting the traversal at `Y` visits `Y, Z, X`, which puts `Z` ahead of its prerequisite `X`. The finished list for that run is `Z, Y, X`, and reversed it gives `X, Y, Z` — correct. Note this variant assumes the graph is already known to be acyclic.
code
pseudocode · 13 linesvisit(u):
visited[u] = true
for each v in adj[u]:
if not visited[v]:
visit(v)
append(finished, u) // only after every successor is done
finished = empty list
for each u in V:
if not visited[u]:
visit(u)
order = reverse(finished)go deeper
Remember the shape: recurse into successors first, record the node when the call returns, reverse the recorded list at the end. Be able to say that the recorded list comes out backwards and that one reversal fixes it.
Justify the reversal from the invariant — a node is recorded only after every successor is recorded, so every edge points backwards in that list. Have a two-prerequisite counterexample ready showing why visit order fails.
Discuss what the variant does not give you: no cycle signal, a recursion depth equal to the longest path, and no control over which of many valid orders you get. Say when you would reach for the iterative in-degree form instead.
Own the consequence of non-uniqueness across a system. If downstream consumers cache, log or compare against a produced order, the freedom in the algorithm becomes a correctness-adjacent risk, and someone has to decide whether the order is a contract or an implementation detail.
## Setting the convention Say a certification track has modules, and module `M` lists prerequisite modules. Draw the edge from the prerequisite to the module that requires it: `X -> Z` means "finish X before Z". A valid study plan is a topological order under that convention. ## The two orders a traversal produces A depth-first traversal touches each node twice in a meaningful sense: - **Visit (pre-) order** — the sequence in which nodes are first entered. - **Finishing (post-) order** — the sequence in which their recursive calls return. They are genuinely different sequences and only one of them is useful here. ## Why finishing order is exactly backwards The recursion appends a node only after the loop over its successors has completed. So when `u` is appended, every node reachable from `u` is already in the list. Restate that as a claim about the pair on any edge `u -> v`: when `u` is being finished, `v` has either just been finished inside `u`'s own loop, or was finished earlier in the traversal. Either way **`v` appears before `u` in the finished list.** (The "or was finished earlier" case is where acyclicity is doing work: in a DAG, an already-visited `v` cannot still be in progress up the call stack, because that would mean a path from `v` back to `u`.) So in the finished list every edge points *backwards*. Reverse the list once and every edge points forwards — which is the definition of a topological order. That is the entire justification, and it is the one an interviewer wants said in a sentence. ## Why visit order does not work A counterexample settles it faster than argument. Two independent prerequisites feed one module: `X -> Z` and `Y -> Z`. If the outer loop happens to start at `Y`, the traversal visits `Y`, descends into `Z`, and finishes; then the outer loop picks up `X`, whose only successor is already visited. Visit order is `Y, Z, X` — and `Z` sits ahead of `X`, violating a prerequisite. Finishing order is `Z, Y, X`; reversed, `X, Y, Z`, which is valid. Preorder simply has no relationship to "all my predecessors are done", because the traversal does not know a node's predecessors when it first arrives. ## Two things this does not tell you **The starting node does not need to be a source.** The outer loop can iterate the nodes in any order and start a traversal at any unvisited node; the argument above never assumed the traversal began at an in-degree-zero node. This surprises people who have internalised the in-degree method, where seeding sources is mandatory. **The order is not unique.** Change the outer loop order, or the order successors are enumerated, and you get a different — equally valid — result. A DAG with several unrelated modules has many valid study plans; "the topological order" is a phrase to distrust. The order is unique precisely when at every step exactly one node is available with all predecessors done — equivalently, when the DAG contains a path visiting every node, so that consecutive nodes are pinned by an edge. Otherwise the freedom is real and any consumer relying on a particular sequence is relying on an implementation detail. ## Practical notes Cost is O(V + E): each node is entered once, each edge is followed once. Space is O(V) for the visited marks and the output, plus the recursion stack — and that stack is part of the space complexity, which matters because its depth is the longest path in the graph. A dependency chain thousands deep will exhaust it, and the usual remedy is an explicit stack rather than recursion. Finally, this variant **presumes acyclicity**. It happily produces a plausible list on a cyclic graph, because appending on return does not notice that a successor was still in progress. If the input is not guaranteed acyclic, verify separately — for instance by running the in-degree method and checking that it emits every node — before trusting the result. ## Choosing between the two variants Both are O(V + E). The recursive one is shorter to write and naturally produces the reversed list. The in-degree one is iterative (no stack-depth ceiling), gives a cheap completeness check for cycles, and exposes the ready set explicitly, which is what you need when you want to control tie-breaking or hand ready work to parallel workers. Say which you would pick and why; "either, they are both linear" is a weaker answer than a reason.
- Does the outer loop's choice of starting node affect correctness?No. The argument only uses "a node is appended after all its successors", which holds no matter where a traversal begins, so any unvisited node is a legal start. What the choice does affect is which valid order you get. That is a real consequence when a consumer depends on the sequence, but it is a determinism concern, not a correctness one.
- Is the topological order of a DAG unique?Almost never. Any two nodes with no path between them can appear in either relative position, so a graph with independent branches has many valid orders. Uniqueness holds exactly when at every step precisely one node has all its predecessors satisfied — equivalently when a single path visits every node, pinning consecutive pairs by an edge. Treat a specific order as an implementation detail unless you deliberately fix it.
- When would you choose the in-degree method over this recursive one?When you need a cheap cycle check (compare emitted count to node count), when you want to control which ready node goes next for deterministic output, when the ready set itself is the product because workers can run those items concurrently, or when the graph's longest path is deep enough that recursion depth becomes a risk. Both are O(V + E), so the choice is about these properties, not speed.
Unpacking nested boxes: you can only declare a box "done" after every box inside it is done. Writing down the boxes as you finish them lists the innermost first, so reading the list backwards gives the order in which you would have had to pack them.
saying these in an interview costs you the question
- Claims the visit sequence is already a valid order
- Says the traversal must start at a prerequisite-free node
- Assumes the topological order is unique
- Forgets this variant presumes the graph is acyclic
- Ignores recursion depth as part of space cost