TOPO-SORT: run DFS, output vertices in decreasing post[] order
§2 — The Idea, Step by Step
Start — one corridor at a time in a maze. Imagine you are deep inside a hedge maze. The simplest plan is to pick a corridor and follow it as far as it goes. Hit a dead end? Walk back to the last junction you had a choice and try the next unexplored corridor. Keep doing this and you will eventually visit every reachable spot. That “go as deep as you can, then back up and try the next branch” rule is Depth-First Search. (Breadth-First Search does the opposite — it fans out evenly in rings.)
Build — the stack, and two timestamps. A graph is just dots (vertices, written $V$) joined by links (edges, $E$). DFS remembers the path back out using a stack — a last-in, first-out pile, like a stack of plates where you always take the top one first. (Calling a function recursively uses the computer’s call stack for exactly this.) As DFS runs it stamps each vertex twice: a pre number the moment it first arrives, and a post number the moment it has finished every corridor leading out of that vertex and backs away. Worked example: enter room $A$ (pre $=1$), push on to $B$ (pre $=2$), reach a dead-end $C$ (pre $=3$, then immediately post $=4$), back up to $B$ (post $=5$), back up to $A$ (post $=6$). Notice $A$’s interval $[1,6]$ completely contains $B$’s $[2,5]$ and $C$’s $[3,4]$: every descendant nests inside its ancestor.
Deepen — why $O(V+E)$, and what the stamps reveal. Mark each vertex visited the first time you arrive, so you never enter it twice → each vertex is opened once, $O(V)$. From each vertex you scan its outgoing links, and across the whole run every edge is looked at from both endpoints → $O(E)$. Together the cost is $O(V+E)$, linear in the graph, and the working memory is the depth of the deepest path, $O(h)$. The timestamps do real work: an edge from $u$ to an ancestor still on the stack is a back edge, and a back edge exists if and only if the graph has a cycle — no back edges means it is a DAG. And for a DAG, listing the vertices by decreasing post-number gives a valid topological sort, because for any edge $u\to v$ DFS always finishes $v$ before $u$ (so $\text{post}[v]<\text{post}[u]$). One warning: DFS does not find shortest paths — it may wander down a long corridor before reaching a target that was one step away.
Try this in the panel above. The animated panel is a generic step-through demo of an algorithm trace. Use ▶│ Next to advance a single operation and ◀ Back to retrace it, so you can follow the explore-then-backtrack rhythm at your own pace. Press Play, then drop the speed to 0.25× to watch each step settle before the next fires. Finally, drag the n slider to a new size and press Reset to launch a fresh trace from the start.
§3 — Algorithm Analysis & Derivation
Symbol
Meaning
n
Input size (vertices V, edges E, or array length)
T(n)
Time complexity function
W(n)
Worst-case complexity
A(n)
Average-case complexity
h
Height or depth of structure
k
Number of distinct values / items
Step 1 -- Explore-then-backtrack. DFS follows one path as deep as possible before backtracking. Each vertex gets a pre-order timestamp (when first visited) and a post-order timestamp (when fully explored). These timestamps encode the DFS tree structure.
Step 2 -- Time Complexity. Each vertex visited exactly once: O(V). Each edge examined exactly twice: O(E). Total: O(V+E). Same as BFS but different traversal order.
Step 3 -- Edge Classification. In DFS, edges are classified as: Tree edges (DFS tree). Back edges (v is ancestor of u -- cycle in directed graph). Forward edges (v is descendant, not child). Cross edges (neither ancestor nor descendant). Undirected graphs have only tree and back edges.
Step 4 -- Cycle Detection. Directed graph has a cycle if and only if DFS finds a back edge (edge to an ancestor in DFS tree). Undirected: cycle if DFS finds a back edge to any non-parent visited vertex.
Step 5 -- Topological Sort. A DAG's topological order = vertices sorted by decreasing post-order timestamp. Proof: if edge u->v exists, DFS on u will finish v before u (post[v] < post[u]). So decreasing post-order gives valid topological order.
Pre-order timestamp: assigned when DFS first visits vertex u. Post-order: assigned when DFS finishes exploring ALL paths from u (backtracks). The [pre,post] interval of a vertex u contains [pre,post] of all its descendants -- the nesting property.
When does DFS find shortest paths? concept+
DFS does NOT find shortest paths in general. DFS may take a long detour before finding the target. Only in special cases (tree = no cycles, unweighted) does DFS path equal shortest. For shortest paths, use BFS (unweighted) or Dijkstra (weighted).
Where is DFS used in compilers and build systems? applied+
Topological sort via DFS determines compilation order -- if module A imports B, B must be compiled first. Make and CMake use this. Import cycle detection in Python/Java. Dead code elimination via reachability DFS from entry point.
What is a back edge and why does it indicate a cycle? concept+
A back edge in DFS goes from u to an ancestor v (v is still on the current DFS stack -- gray). This means there is a path from v to u (via DFS tree) and an edge from u to v -- forming a cycle. No back edges = DAG.
How does DFS detect strongly connected components? nonobv+
Kosaraju: run DFS on original graph, record finish times. Transpose graph (reverse all edges). Run DFS in decreasing finish-time order on transposed graph -- each DFS tree is one SCC. Intuition: in original graph, SCC is reachable; in transpose, reachability is reversed, separating SCCs.
What is the difference between recursive and iterative DFS? deep+
Recursive DFS: elegant, uses call stack (O(h) space). Iterative DFS with explicit stack: avoids stack overflow for deep graphs. BUT: iterative DFS with a stack does NOT automatically give post-order timestamps. Must explicitly track when all neighbors are processed to record post-order.
§5 — Common Misconceptions & Errors
Conceptual Misconceptions
✗ DFS gives the shortest path.
✓ DFS does NOT guarantee shortest path. BFS gives shortest path (fewest edges) in unweighted graphs.
✗ All edges in DFS are tree edges or back edges.
✓ In directed DFS, there are also forward edges (to descendants) and cross edges (to different subtrees). Only undirected DFS has just tree and back edges.
✗ Topological sort works on any directed graph.
✓ Topological sort requires a DAG (Directed Acyclic Graph). A graph with cycles has no valid topological ordering.
Implementation Errors
✗ Recursive DFS works for graphs with thousands of vertices.
✓ Recursive DFS can cause stack overflow for deep graphs (path graph with n=10^5). Use iterative DFS with explicit stack for large inputs.
✗ Not handling disconnected graphs -- running DFS only from vertex 0.
✓ For disconnected graphs, must run DFS from every unvisited vertex to traverse all components.
✗ Forgetting to handle the post-order timestamp in iterative DFS.
✓ Iterative DFS does not automatically compute post-order. Must explicitly push a 'return marker' on the stack to record when all neighbors are processed.