Depth-First Search (DFS)

Solving a maze with one hand on the wall, walking a directory tree, checking a dependency graph for loops: all of them dive as deep as possible and back up only when stuck. That is depth-first search.

intermediate⏱ 12 min read

←Builds on

0Recursion & the Call StackRecursive DFS lets the call stack remember the way back.3Stack (LIFO) & Expression EvaluationSwap the queue of BFS for a stack and the wave becomes a dive.4Backtracking & Pruning: N-QueensDFS goes deep and backs up exactly like a backtracking search.

Leads to→

6Cycles, Topological Sort, Bipartite CheckCycle detection and topological order are read off DFS entry and exit times.8Union-Find (DSU)DSU answers "connected?" like DFS on components, but stays fast while edges keep arriving.10DP on TreesEach vertex's answer is computed when DFS leaves it, after all its children.

1Learn 2Play 3Check 4Practice

Learn

The idea, the mechanics and the cost.

01Go deep, then back up

BFS spreads like a wave; DFS behaves like a curious explorer. From the current vertex it steps to any unvisited neighbour and keeps going. When a vertex has no unvisited neighbours left, it backtracks to the vertex it came from and tries that vertex’s next neighbour.

On the same tree, BFS numbers the vertices level by level, while DFS finishes a whole branch before it touches the other side.

The natural implementation is recursion, so the call stack does the bookkeeping: void dfs(int v) { used[v] = true; for (int to : g[v]) if (!used[to]) dfs(to); }. It is BFS with the queue replaced by a stack. DFS does not find shortest paths, but it reveals structure: cycles, components, an order for tasks, bridges.

The numbers are the visiting order on the same tree.

02Colours and timestamps

Like BFS, DFS colours its vertices: white = not visited, gray = entered but not finished (it is on the recursion stack, on the current path), black = finished. Add a global clock and record two times:

tin[v]: when v turns gray (we enter it);
tout[v]: when v turns black (all its neighbours are done).

The figure runs DFS on the graph from the BFS lesson, starting at 4 and scanning neighbours in list order. It goes 4 → 5 → 7 → 9, backs up to 7, goes on to 1, and there it sees 5, which is gray and is not 1’s parent: a back edge. In an undirected graph a back edge always closes a cycle, here 5 → 7 → 1 → 5. Edges that discover a new vertex are tree edges; together they form the DFS tree.

Each vertex is entered once and each adjacency list scanned once: O(V + E).

DFS on the BFS lecture’s graph from 4: badges show tin/tout.

03The parenthesis structure

Write “(v” when you enter v and “v)” when you leave it, and the whole DFS reads like correctly nested brackets. In terms of intervals: for any two vertices the intervals [tin, tout] are either disjoint or one contains the other; they never partly overlap.

That gives an O(1) ancestor test: u is an ancestor of v in the DFS tree exactly when tin[u] < tin[v] and tout[v] < tout[u]. In the figure, 5’s interval [2, 9] contains 7’s [3, 8], which contains 9’s [4, 5] and 1’s [6, 7]; 2 [10, 13] and 3 [14, 17] are separate branches.

The same timestamps drive later algorithms. Topological sort uses the order of tout; bridges and articulation points compare tin with the lowest reachable tin; and the Euler tour trick turns every subtree into a contiguous range [tin, tout], ready for prefix sums or a segment tree.

04Components, iterative DFS and pitfalls

One call dfs(s) visits exactly the vertices reachable from s. To find all connected components of an undirected graph, loop over the vertices and start a new DFS from every vertex that is still unvisited, counting the starts. The total stays O(V + E), because over all calls each vertex is visited once. The same loop counts islands in a grid or rooms in a floor plan.

Pitfalls:

deep recursion: a path of 10⁶ vertices means 10⁶ nested calls and a stack overflow in many environments; then write DFS with an explicit stack<int>, or raise the stack limit;
a single used flag cannot tell gray from black; detecting a cycle in a directed graph needs all three colours;
DFS paths are not shortest; for distances use BFS.

Cost at a glance

TimeO(V + E)

Memory (recursion depth up to V)O(V)

Ancestor test with tin/toutO(1)

All connected componentsO(V + E)

Remember

DFS dives to an unvisited neighbour and backtracks when stuck; recursion, which is a stack, does the bookkeeping.
Entry and exit times nest like parentheses, which gives O(1) ancestor tests and drives cycle detection and topological sort.
Looping “if unvisited, start a new DFS” finds all connected components in O(V + E).

Play

Step through the algorithm, then try it on your own input.

👀 What to watch: Watch the call stack: it is exactly the gray path from the start to the current vertex. The badges show tin/tout as they are stamped. Try other start vertices.

Interactive visualizerfocus here, then space ← →

Graph (DFS, source: 4)

gray: on the pathblack: finished

Call stack

(empty)

Timestamps

v	1	2	3	4	5	6	7	8	9
tin	·	·	·	·	·	·	·	·	·
tout	·	·	·	·	·	·	·	·	·

DFS explores as deep as possible before backing up. It’s BFS with the queue replaced by a stack (here, the recursion stack). Start at 4.

Pseudocode

 1 dfs(u): 2   color[u]=gray; tin[u]=++t   // enter 3   for w in adj[u]: if white → tree edge, recurse 4     else if gray & not parent → BACK EDGE (cycle!) 5     else skip (parent edge or already finished) 6   color[u]=black; tout[u]=++t   // exit

1 / 1

Check

Three questions. Pick an answer to see why.

In an undirected graph, DFS at u sees a neighbour w that is gray and is not u’s parent. What does it mean?

Timestamps: u = [2, 9], v = [4, 5], w = [10, 13]. Which statement is true?

Which task needs BFS rather than DFS?

Practice

Real problems to lock it in, easiest first.

LeetCodeFlood Fill beginner↗CSESCounting Rooms beginner↗CSESBuilding Roads intermediate↗LeetCodeMax Area of Island intermediate↗LeetCodeClone Graph intermediate↗