Intermediate · Module 17 · Lesson 2
Depth-first search
Explore a branch fully; detect structure recursively.
Lesson 96 of 123
1d streakInteractive Visualization
Trace the algorithm state by state
Change the inputs, run an operation, and connect each visible state change to the explanation below.
Interactive algorithm lab
Depth-First Search
Stack-driven branch exploration
Current
—
Stack
A
Visited
0
Order
—
Why this step happens
Start at A and place it in the stack.
The stack contains branches that are discovered but not fully explored.
Depth-First Search (DFS): Connected Components & Cycle Detection
Graph DFS explores deep along paths until a dead end is reached, then backtracks. It operates in O(V + E) time and is the backbone of connected component counting, island problems, and path existence queries.
public int numIslands(char[][] grid) {
int count = 0;
for (int r = 0; r < grid.length; r++) {
for (int c = 0; c < grid[0].length; c++) {
if (grid[r][c] == '1') {
count++;
dfs(grid, r, c); // Sink connected landmass
}
}
}
return count;
}
private void dfs(char[][] grid, int r, int c) {
if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || grid[r][c] != '1') return;
grid[r][c] = '0'; // Mark visited in-place
dfs(grid, r + 1, c);
dfs(grid, r - 1, c);
dfs(grid, r, c + 1);
dfs(grid, r, c - 1);
}Active Recall Checkpoint
What risk does recursive DFS carry on large grids (e.g. 10,000 x 10,000)?
Show answer & explanation
Deep recursion can trigger java.lang.StackOverflowError. Iterative DFS with an explicit Stack on the heap or BFS prevents call-stack overflow.
Use it when
Use DFS for topological sort, cycle detection in directed graphs, strongly connected components, flood fill, and island counting.
Reconsider when
Reconsider when seeking the shortest path between two nodes in unweighted graphs (use BFS).
Cost Model
Complexity & Trade-offs
When to use it
- Networks, dependencies, connectivity, shortest paths, and grid movement.
- Ordering prerequisite-constrained work.
- Grouping reachable or mutually reachable states.
Common mistakes
- Marking visited too late and enqueuing the same vertex repeatedly.
- Ignoring disconnected components.
- Using an algorithm whose weight assumptions do not match the graph.
Practice prompts
- Reproduce the worked Depth-first search example without looking at the trace.
- Change one input condition and explain whether the Depth-first search invariant still holds.
- Implement the approach, derive its cost, and compare it with a straightforward baseline.
Mastery check