Depth-First Search

Depth-first search (DFS) is a graph traversal algorithm that follows one branch as far as it goes before backing up to try the next, using a stack — most naturally the recursion call stack — to remember the way back. It visits every reachable vertex and edge once, in O(V + E) time, and is the backbone of cycle detection, topological sort, and connectivity.

Picture walking a maze with a ball of string. At every fork you commit to one passage, paying out string behind you, and you ignore the other passages entirely — for now. Hit a dead end and you rewind string back to the last fork, then take the next untried passage. The string is the call stack, and rewinding it is backtracking: the half of DFS that beginners forget exists.

How Depth-First Search Works

Recursive DFS is four lines of idea: mark the current node and record it; for each neighbour, if it is unvisited, recurse into it; when the loop ends, return. The return is the algorithm's second half — every descent is eventually paid back by an ascent to the caller, and the deepest frame on the call stack is always where you are standing right now.

This lesson runs in two modes, and the animated code changes with the mode. In Tree mode there is exactly one path to every node, so a revisit is impossible — the displayed tree code honestly carries no visited set at all, just append, recurse, return. In Graph mode edges can reconverge or form cycles, so visited returns as the guard: each call marks its node on entry, and the neighbour loop recurses only into unmarked nodes. An edge aimed at an already-visited node gets classified instead of followed: if the target is still on the call stack (an ancestor — string still paid out through it), it is a back edge, the smoking gun of a cycle; if the target has already finished, it is a forward edge when it was discovered inside the current call's subtree (a descendant) and a cross edge otherwise. DFS skips all three.

Depth-First Search Step by Step

The default configuration is Graph mode, Cyclic preset, starting at node 0 — a 6-node directed graph with cycles wired into it: 0 → [1, 3], 1 → [2], 2 → [0, 4], 3 → [4, 5], 4 → [5], 5 → [1]. The cycles are the point. This is the run where the visited guard stops being decoration and becomes the only thing keeping the search finite.

1. dfs(0) — mark 0 (#1). Stack: [0]. First neighbour 1 is unvisited → recurse.
2. dfs(1) — mark 1 (#2). Stack: [0, 1]. Recurse into 2.
3. dfs(2) — mark 2 (#3). Stack: [0, 1, 2]. First neighbour is 2 → 0, but 0 is visited and still on the stack — a back edge, the smoking gun of a cycle. Skip it. (Follow it and dfs(0) would recurse forever.) Next neighbour 4 is unvisited → recurse.
4. dfs(4) — mark 4 (#4). Stack: [0, 1, 2, 4]. Recurse into 5.
5. dfs(5) — mark 5 (#5). Stack: [0, 1, 2, 4, 5] — the deepest the string gets. Its only neighbour is 5 → 1; 1 is on the stack → another back edge, skipped. 5 is done → return, and the string rewinds 5 → 4 → 2 → 1 back up to node 0.
6. dfs(3) — back in 0's loop, its second neighbour 3 is still unvisited → mark 3 (#6). Stack: [0, 3]. Now 3 → 4 and 3 → 5 both point at nodes already finished and off the stack — cross edges, skipped all the same. 3 is done → return to 0; 0 is done. Search ends.

Visit order: 0, 1, 2, 4, 5, 3. Four edges never got walked, and the whole lesson lives in the distinction the visited check draws between them. 2 → 0 and 5 → 1 are back edges — they aim up at an ancestor still on the call stack, and each is a cycle caught red-handed. 3 → 4 and 3 → 5 are cross edges — they aim at a node whose work already finished. DFS skips both, but only the back edges would have looped forever; the cross edges are merely redundant. That difference — still on the stack versus already done — is the entire mechanism of cycle detection, and it is exactly what an acyclic tree can never show you.

The other presets strip the picture down on purpose. Tree mode (Balanced or Skewed) removes cycles entirely: with one path to every node the visited check never fires, every edge is a tree edge, and what is left is pure depth-first order — on the balanced 7-node tree (0 → [1, 2], 1 → [3, 4], 2 → [5, 6]) that order is 0, 1, 3, 4, 2, 5, 6, node 1's entire subtree finished before sibling 2 is ever touched, the exact opposite of BFS's level-by-level 0, 1, 2, 3, 4, 5, 6. The graph Simple preset keeps a single cross edge and no back edge — the gentlest taste of the guard. Reach for those to isolate the traversal order from the cycle-handling; the default shows both at once.

On the canvas, the focus ring does the walking: it slides down an edge when a call descends and back up when one returns, while the call-stack panel on the right grows and shrinks frame by frame in sync. Nodes are faint blue until reached, orange while their call sits on the stack (the current call at full strength, waiting ancestors dimmed), and green once finished; a skipped back, forward, or cross edge flashes red the instant the loop rejects it. The green region spreading as the stack unwinds is the rewinding string.

Time and Space Complexity

Each vertex is entered once (the visited mark makes "once" true) and each edge is examined once from its tail. Space is the call stack plus, in graph mode, the visited set. The stack holds one frame per node on the current root-to-here path, which degenerates to O(V) on a single long chain — exactly the shape where DFS is expensive and BFS's queue stays tiny. The visited set keeps one mark per reached node, O(V) on any graph. On the stack side, the two algorithms pay their O(V) in opposite dimensions.

Edge Cases

• Single node, no edges — dfs(start) marks it, finds no neighbours, returns immediately.
• Unreachable nodes — DFS reaches only the nodes the start can reach along directed edges (in an undirected graph, its connected component); the rest stays unvisited. Covering everything means restarting from each still-unvisited node.
• Cycles — the visited check converts the cycle's closing edge into a skipped back edge, so the recursion terminates.
• Deep, chain-like input — the call stack grows as tall as the path. In production code this is where recursive DFS overflows the runtime stack and an explicit stack version takes over.

Common Mistakes

1. Dropping the visited check on a graph. Any cycle then pulls the recursion around forever. (Only a genuine tree earns the guard-free version the Tree mode displays.)
2. Marking visited too late. Mark the node the moment you enter dfs(node), before touching its neighbours — mark it after the loop and a cycle can re-enter the node while its call is still running.
3. Forgetting that backtracking is half the algorithm. DFS is descent and return; algorithms built on DFS (topological sort, finish times, articulation points) do their real work on the way back up the string.
4. Assuming one "correct" order. Visit order depends on how the adjacency lists are written: 0 → [1, 2] and 0 → [2, 1] produce different, equally valid DFS traversals.
5. Confusing DFS with BFS. Stack versus queue is the entire difference — swap the container and depth-first becomes breadth-first.