Graph Traversal¶
Also known as: BFS/DFS on Graphs, Flood Fill, Connected Components, Grid-as-Graph
A grid is a graph in disguise — every cell is a node and its neighbours are its edges. Once you see that, "count the islands" and "find the shortest path" become the same two algorithms you already met on trees, plus one new obligation: mark what you've visited, because unlike a tree, a graph can walk you in circles.
Before you start¶
What 'solved properly' looks like
Target: O(V + E), or O(m × n) for a grid. If your solution is slower than that, you've found a solution but not this pattern — the judge says "Accepted" either way, so treat this as your real benchmark.
The idea¶
You traverse the graph exactly like you traversed trees — DFS with a stack (or recursion) and BFS with a queue — but you add one critical piece: a visited set. Before processing any node, you check whether you've already seen it. If yes, you skip it. That single addition is what makes tree algorithms work on graphs, where cycles can otherwise send you into an infinite loop.
Why it matters: More real problems are graphs than people expect — maps, dependencies, networks, images, mazes — and the trees you already learned were only the easy special case. Recognising a grid as a graph of cells, or a social network as a graph of people, is the conceptual leap.
When to reach for it¶
Reach for it when you see islands or regions in a grid, connected components, shortest path in an unweighted graph, reachability, flood fill, or multi-source spread problems like "rotting oranges."
When not to use it
Forget the visited set and you loop forever — this is the graph bug. For shortest paths in an unweighted graph you must use BFS, not DFS; DFS finds a path, not the shortest, and the difference is invisible on small test cases. If edges carry weights, neither BFS nor DFS works — that's Dijkstra.
Practice set¶
Work these top to bottom. The time-box is a cue to pause and re-read the triggers above if you're still stuck when it passes — not a deadline to race. Getting unstuck by stepping back is the skill being trained.
| # | Problem | Where | Difficulty | Time-box | Role |
|---|---|---|---|---|---|
| 1 | Flood Fill | LeetCode | Easy | 15 mins | teaching |
| 2 | Number of Islands | LeetCode | Medium | 20 mins | teaching |
| 3 | Max Area of Island | LeetCode | Medium | 20 mins | consolidation |
| 4 | Rotting Oranges | LeetCode | Medium | 25 mins | consolidation |
| 5 | Pacific Atlantic Water Flow | LeetCode | Medium | 35 mins | challenge |
Already know this? Test out.
If you can solve Pacific Atlantic Water Flow cleanly in one sitting — running BFS or DFS from both oceans and computing the intersection — you already own this pattern, so move on to the next one. If it tangles you up, that's your signal to work the set from the top instead of skipping.