Depth-first search — every question, written out
Follows one path as deep as it goes, then backtracks. The call stack is the data structure. Cycle detection, topo sort and maze-solving fall out of it.
Read the depth-first search explanation and watch it run
Why is DFS O(V + E) even though the recursion can nest deeply?
Complexity derivation
Depth costs stack, not work: each node is visited once and each edge inspected once per endpoint
The visited set admits each node to exactly one `visit` call, giving V frames pushed and V popped. Inside each call the adjacency list is walked once, and summing those lengths over all nodes gives 2E on an undirected graph. Depth changes how much stack is live at a time, which is a space cost, and leaves the time bound untouched.
See it run — The finished run: 12 frames pushed for 12 nodes, and 26 edge inspections for 13 edges.
On Prism’s default graph DFS records 11 tree edges and 15 rejections. Why is the split fixed at 11?
Complexity derivation
Exactly one edge discovers each node other than the start, so tree edges always number V − 1
Every node except the start is entered through exactly one edge — the one that discovered it — so the tree edges form a spanning tree with V − 1 = 11 of them. The other 15 of the 26 inspections find a node already visited and reject. BFS on the same shape produces the same split, because both build a spanning tree; only which edges get chosen differs.
DFS is advertised as the memory-cheap traversal. What is its actual worst-case space?
Complexity derivation
O(V), because a path-shaped graph puts every node on the call stack simultaneously
DFS and BFS have the same O(V) space bound; they differ in what fills it — deepest path versus widest level. The practical difference is that DFS spends it on the call stack, which most runtimes cap far below the heap, so the failure mode is a stack overflow rather than an allocation error. On a wide shallow graph DFS wins comfortably; on a long chain it is the one that crashes.
So you rewrite it iteratively with an explicit stack. What changes besides the crash?
Trade-off & selection
The visit order flips within each node’s neighbours, because a LIFO stack pops them in reverse
Both versions explore exactly the same nodes and the same edges, so correctness and complexity are untouched. What changes is the sequence: recursion descends into the first neighbour, while the explicit stack descends into the last one pushed, so any test asserting a traversal string will fail until you push in reverse. Postorder also stops being free — you need an explicit marker on the stack to know when a node’s subtree is finished.
The frame panel shows six live frames. What exactly do those six nodes represent?
Invariant identification
The current path from the start to the active node — every frame is an ancestor of the one below
A frame stays live exactly while that node is mid-loop over its neighbours, so the live frames are precisely the chain of calls that led here. That is why the panel is drawn beside the graph: the stack *is* the highlighted path, knot for knot. Almost every classic DFS extension — cycle detection, articulation points, strongly connected components — is a question about this chain rather than about the visited set.
See it run — Six frames are live — A, B, D, G, L, E — and that is the path currently drawn on the graph.
A directed-graph cycle detector reports a cycle whenever DFS meets any visited node. Why is it wrong?
Code diagnosis
A finished node proves nothing — the cycle test is whether the node is still on the stack
Two paths converging on a node is not a cycle: if that node has already finished, everything below it was explored and returned, so there is no route back up to the current path. A cycle requires reaching a node that is an ancestor of where you stand, which is precisely "still on the stack" — the grey state in white–grey–black colouring. Testing merely-visited reports a cycle on any diamond-shaped DAG, which is the most common shape in a real dependency graph.
Now the graph is undirected. Applied unchanged, the on-stack test fires on every single edge. Why?
Code diagnosis
Each edge appears in both adjacency lists, so a child always sees its parent, still on the stack
The edge that discovered a node reappears when that node walks its own neighbours, pointing straight back at its parent — which is by definition on the stack. Excusing the immediate parent fixes it, and then any remaining visited neighbour genuinely closes a cycle. The trace shows exactly this: the first thing B does after being discovered by A is inspect the edge back to A and reject it.
See it run — B’s first inspection is the edge back to its own discoverer A — the parent edge, rejected.
A node’s frame pops last of all, at the very end of the run. What does that tell you?
Invariant identification
Everything reachable from it finished first — a node is done only when its whole subtree is done
A frame cannot return until its neighbour loop is exhausted, and each of those neighbours recursively did the same — so finishing is a statement about a whole reachable region, not about one node. That single property is the engine behind two classics: reverse finish order on a DAG is a topological sort, and finish order on the reversed graph gives Kosaraju’s strongly connected components. Preorder tells you when DFS arrived; postorder tells you when it was allowed to leave, and the second is the more useful number.
See it run — The start node’s frame pops last, after all eleven others have already finished.
DFS reaches a node whose every neighbour is already visited. What happens next?
Trace prediction
The node is marked finished, its frame pops, and the search resumes in the caller’s loop
A dead end is unremarkable in DFS: the loop simply ends, the node turns from active to finished, and control returns to whoever called it, mid-loop. In the trace, C is discovered, inspects its one remaining neighbour, finds it visited, and pops three steps later. The caller then continues to its own next neighbour as if nothing had happened.
See it run — C’s frame pops immediately after its only unexplored edge is rejected — control returns to B.
The trace visits E at stack depth six. If a two-edge route to E also existed, would DFS have found it?
Trace prediction
Not necessarily — the first arrival wins, and DFS arrives by whichever branch it committed to first
DFS commits to a branch and exhausts it before considering the alternatives, so the route it records is the first one its neighbour ordering happened to produce. A one-edge shortcut sitting in the start node’s adjacency list may not be examined until the entire first branch has finished. That is the whole reason DFS answers "is it reachable" and never "how far is it".
See it run — E is entered at depth five, via A → B → D → G → L, rather than by any shorter route.
On the islands preset DFS finishes with six of twelve nodes visited. What does a correct component count add?
Edge case reasoning
An outer loop over every node that launches a fresh search whenever one is still unvisited
One `visit(start)` explores precisely the component containing the start, which on this preset is six of twelve nodes. Wrapping it in "for each node, if unvisited, visit it and increment a counter" turns the traversal into a component counter with no change to the traversal itself. It is the fix for every islands-and-regions problem, and it is invisible on connected test data.
See it run — The run ends with A–F finished and the second island never touched — five tree edges, not eleven.
Recursive DFS works on your tests and crashes on production data with a million nodes. Why, and what is the fix?
Edge case reasoning
A long chain nests the recursion a million deep; rewrite it with an explicit stack on the heap
Recursion depth tracks the longest path DFS takes, which on chain-like real data can approach V, and most runtimes overflow somewhere between ten thousand and a hundred thousand frames. Python is worst-hit with a default limit near a thousand, and raising it trades a clean exception for a segfault. Moving the frames to an explicit heap-allocated stack keeps the same O(V + E) and the same visited set, at the cost of managing the neighbour index yourself.
Backtracking searches unmark state on the way out; graph DFS does not. What breaks if you swap them?
Trade-off & selection
Unmarking on return re-explores every node once per path, turning linear traversal exponential
Graph traversal asks "has this node ever been explored", so the mark must outlive the path — a node explored once is finished forever. Backtracking asks "is this choice currently in use", so the mark must be undone when the choice is unmade, or later candidates are blocked by decisions that were already abandoned. The two share a code skeleton and differ in exactly one line, which is why importing the wrong convention produces either exponential blowup or missing answers.
You need to know only whether a path exists between two nodes. Which traversal, and why?
Trade-off & selection
Either is correct; DFS is usually preferred because it holds one path rather than a whole level
A pure yes-or-no reachability question makes no use of BFS’s distance guarantee, so the decision falls to memory and constant factors. DFS keeps one root-to-node path alive, which on a wide graph is dramatically smaller than a level of the frontier, and it is a few lines shorter as recursion. The caveat is the stack depth: on very deep graphs the memory argument reverses and BFS becomes the safe choice.
Two DFS implementations return different node sequences on the same graph. Is one of them wrong?
Comparison
Not necessarily — neighbour order and container discipline both change the sequence, not the reachable set
DFS is defined by its discipline, not by a unique output: from a node it descends into some unvisited neighbour, and which one is a free choice. Prism sorts adjacency lists alphabetically so the drawing is reproducible, and an iterative rewrite that pushes those same neighbours onto a stack pops them in reverse. Both are valid depth-first traversals, which is why tests should assert on properties rather than on a traversal string.
Both traversals are O(V) space. On a game tree with branching factor 30 and depth 12, which survives?
Comparison
DFS — it holds 12 frames, while BFS would have to store the entire bottom level at once
The O(V) bound is the same for both and tells you nothing here; the shape of what fills it decides. DFS stores one root-to-leaf path, so 12 frames, while BFS stores a complete level, which at branching factor 30 is astronomically large. This is exactly why game and puzzle search uses iterative deepening — repeated DFS with a growing depth cap — to buy BFS’s shortest-solution guarantee at DFS’s memory cost.
Explain DFS to someone who has never programmed. Say it out loud before revealing.
Explain it plainly
Imagine exploring a cave system with a ball of string tied at the entrance. At every junction you pick a tunnel you have not tried and walk down it, letting the string out behind you. When you hit a dead end, you follow the string back to the last junction that still has an untried tunnel and take that one instead. Carry on until every junction you can reach has had all its tunnels tried, and you have seen the whole cave. Two things are doing separate jobs here, and mixing them up is the usual mistake: the string tells you how to get back, and a piece of chalk marking each junction you have already entered stops you walking in circles when tunnels loop round. The string alone will not save you from a loop, and the chalk alone will not tell you the way home. Where the picture breaks: a real caver looks down a tunnel and judges whether it seems promising, while this method takes them in a fixed arbitrary order with no judgement at all — and the route it finds to any particular chamber is whatever it stumbled into, not the short way round.
The test is whether the listener could follow the procedure without help. A strong answer separates the two pieces of bookkeeping — the route back and the record of where you have been — because conflating them is the real conceptual error, and it names where the picture stops holding.