You know one way to produce a topological ordering. Kahn's algorithm works from the front: find ready nodes, process them, let the ripple of decremented in-degrees propagate through the graph. It's clean. It's BFS-flavored. And it requires knowing every node's in-degree before you start.

Scrub through Kahn's algorithm below. The queue always holds nodes with in-degree 0 — each removal may cause new nodes to reach zero.

But there's another approach. Instead of working from the front — “who has no dependencies?” — you can work from the back: “who is done with everything they need to do?” This is a DFS perspective. You don't scan for ready nodes. You dive deep, explore everything reachable from a starting node, and figure out the ordering from the pattern of when you finish exploring.

If that sounds vague, good. It will become concrete in about 30 seconds.

Think about packing a suitcase for a trip. You can't figure out the packing order by listing items as you pull them out of the closet — that tells you which drawer you opened first, not which item you need at the bottom of the bag. But if you decide where each item goes and note when you're done deciding — the last item you finish placing is the one that depends on the most other items. That's the item that goes in the suitcase first. The order you finish is the key.

The question is simple: if you run DFS on a DAG, does the order you discover nodes give you a topological ordering? Your intuition probably says yes. Let's test that.

Here's a 7-node DAG. DFS is about to begin from node A. You'll see two columns build in real time: Discovery Order (the order DFS first visits each node) and Finish Order (the order DFS completes each node's subtree).

After the traversal, you'll make a prediction. Which column, reversed, gives a valid topological ordering? Take your time watching the colors change — WHITE means unvisited, GRAY means in-progress (on the call stack), BLACK means finished. The pattern matters more than the speed.

That discovery order looked promising, didn't it? It follows the shape of the graph, tracks your intuition about “what comes first.” But discovery order is an artifact of adjacency list order — it tells you which drawer you opened first, not which item has priority. The same graph with a different adjacency order would produce a different discovery sequence, but the same finish order (up to the choice of starting node).

Finish order encodes something deeper: “I've handled everything I depend on.” When node X finishes, all of X's descendants have already finished. Reversing that sequence puts ancestors before descendants — which is precisely what a topological ordering requires. Discovery order carries no such structural guarantee.

This is one of those subtle distinctions that trips up even experienced programmers. “I ran DFS and reversed the visit order” sounds reasonable until you trace through a graph where it fails. The fix is surgical: track finish times, not discovery times. One boolean difference in what you record; a fundamental difference in correctness.

The discovery/finish distinction is subtle, so let's nail it down.

When DFS discovers a node, it means “I've arrived here.” When DFS finishes a node, it means “I've explored everything reachable from here — every descendant, every path, every dead end. I'm done.”

The finish time encodes a powerful guarantee. If node X finishes before node Y in a DFS traversal of a DAG, then either X is a descendant of Y (X was explored as part of Y's subtree and finished first), or X and Y are in entirely separate subtrees. Either way, X cannot be a prerequisite of Y. Reversing the finish order flips this: Y before X. And since X was never a prerequisite of Y, having Y first is safe.

Discovery order carries no such guarantee. DFS might discover C before D simply because C appeared first in A's adjacency list — not because C has any structural priority over D. The discovery order is an accident of implementation. The finish order reflects the DAG's actual dependency structure.

There's a clean way to see this formally. In a DFS tree on a DAG, every edge falls into one of three categories: tree edges (parent to child), forward edges (ancestor to descendant), and cross edges (between unrelated subtrees). There are no back edges — those would imply a cycle, and we're working with a DAG. For any edge (u, v) in the graph:

• If it's a tree or forward edge, u finishes after v (parent finishes after child). Reversed: u before v. Correct.
• If it's a cross edge, u finishes after v (cross edges go from later-discovered to earlier-finished subtrees). Reversed: u before v. Still correct.

Every edge respects the reversed finish order. That's the proof. No edge type in a DAG can violate it.

The const visited = new Set() you write in DFS code? That's the discovery tracker. The moment you add stack.push(node) at the end of the recursive function — after all neighbors are processed — you're recording the finish time. The entire algorithm is those two bookkeeping steps plus a reversal at the end.

Time to internalize the mechanism. DFS runs again on the same graph, but now you control the stack. When a node finishes — when it turns BLACK because all its children are done — you push it onto the stack.

For the first several finishes, you'll predict which node is about to complete. Pay attention to the call stack: when a GRAY node has no more unvisited neighbors, it's about to finish. That's the signal. Then, once the stack is full, pop it to read the topological order.

The stack is doing something elegant. Each push says “I'm done — everything I depend on is already handled.” The first node to finish (the one with no outgoing edges to unvisited nodes) goes on the bottom. The DFS root — the node that started it all — finishes last and goes on top. Popping the stack reads the ordering from “most dependencies” to “least dependencies.” That's exactly what topological order requires.

If you're thinking “this is just post-order traversal with a stack,” you're right. DFS post-order is the sequence of finish times. Pushing onto a stack and then popping is equivalent to reversing the array. The stack is a physical metaphor for reversal — and it maps directly to the code: stack.push(node) at the end of the recursive function, then return stack.reverse() at the end.

Now connect the visual to the implementation. The graph is on the left; the DFS topological sort code is on the right. Each code line highlights as it executes. At key moments — when stack.push(node) fires, when stack.reverse() runs — you'll predict the result before seeing it.

The topo sort phase fast-forwards through the parts you've already internalized. The interesting predictions are at the boundaries: which node gets pushed, and what does the reversed stack look like?

Every line of that code maps to something you've done by hand. visited.add(node) is the WHITE-to-GRAY transition. The for loop over neighbors is DFS going deep. stack.push(node) is the GRAY-to-BLACK transition — the moment you decided a node was done. And stack.reverse() is the pop sequence from the previous exercise.

The recursive structure handles the bookkeeping automatically. When dfs(neighbor) returns, you know the neighbor's entire subtree is finished. That's the power of recursion: the call stack IS the gray-node tracking system. You don't need a separate “call stack” data structure — the language runtime provides one.

For iterative implementations, you'd need to manage that stack explicitly. But the recursive version is clean enough to fit in your head, and it's the version that appears in most interviews and textbook problems. The key insight: stack.push goes AFTER the for loop, not before. That single placement difference is the difference between discovery order (wrong) and finish order (right).

You now have two algorithms for topological sort. Kahn's works from the front (BFS, queue, in-degree tracking). DFS works from the back (recursion, stack, post-order reversal). Both produce valid orderings. Both run in O(V + E). So when does it matter which one you use?

The short answer: most of the time, it doesn't. For pure “give me a topological ordering” tasks, either works. But the algorithms have different strengths that become relevant in specific contexts.

Kahn's excels when you need to detect whether a valid ordering exists. Cycle detection is a natural byproduct — if the queue starves before all nodes are processed, there's a cycle. It also naturally reveals which nodes can be processed in parallel — at any given step, all nodes in the queue are simultaneously ready, with no dependencies between them. If you're scheduling tasks on multiple processors, Kahn's tells you what can run at the same time.

DFS excels when you're already doing a DFS for another reason — like searching for a path, computing strongly connected components, or evaluating a recursive expression. In those cases, you can extract the topological ordering as a side effect of the traversal you're already performing. No separate pass needed. You tack on stack.push(node) at the end of your existing DFS function and you've got a topo sort for free.

The deeper difference is conceptual. Kahn's thinks forward: “What can I process NOW?” DFS thinks backward: “What have I FINISHED?” Both perspectives produce the same output, but they expose different structural properties of the graph. And as you'll see in the capstone module, the DFS perspective unlocks something Kahn's doesn't: dynamic programming along the topological order.

Here's the honest admission: I spent an embarrassingly long time early in my career thinking DFS discovery order was the right thing to reverse. It's such a natural assumption — “DFS visits things in a reasonable order, so reversing that order should work.” It doesn't. And the graph where it fails is always smaller and simpler than you'd expect. That's why we started this module with the trap.

Three tasks to cement the DFS perspective. A trace, a prediction, and a comparison. All construction — no multiple choice.