Graphs & Grids: BFS and DFS
Intermediate · 24 min read · Problem-Solving Patterns, Graphs
Islands, flood fill, shortest steps in a grid and multi-source BFS.
Graphs have a reputation for being the hardest topic — and they're not, once you see that almost every graph problem is BFS or DFS with a visited set. A grid of land and water is a graph. A course list with prerequisites is a graph. Accounts sharing an email form a graph.
Representing a graph
The DIRS array is the most reused four lines in grid problems — write it once, loop over it, never hand-write four neighbour checks.
DFS: explore everything reachable
The connected-components template: loop over every node; each time you find an unvisited one, that's a new component — explore it fully, marking everything you touch. Count the starts.
BFS: explore in rings of distance
BFS visits nodes in order of their distance from the start, so the first time it reaches a node is by a shortest path (in an unweighted graph). Use BFS whenever the question says "fewest steps", "shortest", or "minimum time".
Multi-source BFS: many starting points at once
When something spreads from several sources simultaneously, put all of them in the queue before starting. BFS levels then measure the distance from the nearest source.
Thinking in reverse
Some problems are much easier from the other end:
DFS or BFS?
Both are O(V + E) — for a grid, O(rows × cols).
Practice ladder
Interview questions
- Why does BFS find the shortest path in an unweighted graph?
- How would you find the distance from every cell to the nearest gate in a grid?
Further reading
Key takeaways
- Find the graph: cells, words, people, accounts — nodes; adjacency, one-letter difference, shared email — edges.
- DFS for components and region properties; BFS for fewest steps.
- Always keep a visited mark; in BFS, mark when you enqueue.
- Multi-source BFS: start from all sources at once to get distance to the nearest.
- Reverse the search (from borders or targets) when "from every cell" would repeat work.