Intuition First: The Paint-Bucket Tool#

Click the paint-bucket tool on one pixel in an image editor and the color floods outward, spilling into every connected neighbor of the same shade until it runs into a border. That flood is a grid traversal: start at one cell, spread to its up/down/left/right neighbors, then to their neighbors, marking each cell as you go so you never flood the same one twice.

Whether the color spreads in expanding rings (BFS) or rushes down one direction before fanning out (DFS), the underlying idea is the same. And the punchline of this article is that a grid is really just a graph wearing a checkerboard costume.

The Concept#

A 2D grid is an implicit graph. You never have to write out an adjacency list, because the edges are implied by the geometry: every cell (r, c) connects to its up, down, left, and right neighbors (and sometimes to the four diagonals in 8-directional problems). Once you see a grid as a graph, every graph algorithm you already know applies to it.

The two traversal strategies divide the work cleanly:

  • BFS (breadth-first search) explores cells in expanding rings of equal distance from the start. The first time BFS reaches a cell it has done so via the fewest steps possible, which makes it the go-to for shortest-path questions on an unweighted grid (e.g., shortest path through a maze, minimum steps to reach an exit).
  • DFS (depth-first search) dives along one path as far as it can go before backtracking. That depth-first character makes it natural for flood fill and connected-component counting. You launch a DFS from each unvisited land cell to mark its entire region, and the number of launches equals the number of regions (e.g., number of islands, number of connected rooms).

The visited set#

Without bookkeeping, BFS and DFS on a grid will loop forever: stepping right then left repeatedly, for instance. The standard fix is a visited boolean grid (or a set of (r, c) tuples) that records every cell already added to the queue or call stack. A cell is added to visited at the moment it is enqueued or recursed into, not when it is processed. This prevents duplicates from being enqueued by multiple neighbors simultaneously.

In problems that let you modify the input (e.g., "number of islands" in-place), you can mark visited by overwriting the cell value (e.g., flipping '1' to '0'), avoiding the extra space of a separate structure.

Bounds check#

Because grid coordinates can step outside the array (negative indices, or row/column ≥ the grid dimension), every candidate neighbor must be validated before access:

plaintext

Combining this with the passability check (grid[nr][nc] == 0 for open terrain, or whatever the domain uses) and the visited check gives the complete pre-condition for enqueuing a neighbor.

Core Operations#

BFS shortest-path skeleton#

  1. Push the start cell into a deque as ((r, c), 0), the cell plus its distance.
  2. Add start to seen.
  3. While the queue is non-empty: pop from the left (popleft), check if it's the goal, then enqueue valid unvisited neighbors with dist + 1.
  4. If the queue drains without finding the goal, return −1 (unreachable).

Using deque.popleft() keeps each step O(1); using a plain list with pop(0) would degrade to O(R·C) per pop.

DFS flood-fill skeleton#

  1. If the current cell is out of bounds, a wall, or already visited, return immediately.
  2. Mark it visited.
  3. Recurse into all four neighbors.

Call this from every unvisited land cell in the outer loop; each call colors an entire connected region.

Code Implementation#

The four directions (1,0), (-1,0), (0,1), (0,-1) correspond to down, up, right, left. They are compact to iterate and easy to extend to 8-directional grids by appending the four diagonal offsets.

The DFS flood-fill skeleton translates just as directly. flood_fill bails on any out-of-bounds, wall, or already-visited cell, then marks the cell and recurses into its four neighbors; count_regions launches one flood from each unvisited land cell, and the number of launches is the number of connected components.

Complexity Analysis#

MetricValueWhy
TimeO(R·C)Each of the R·C cells is enqueued or visited at most once
SpaceO(R·C)The seen set and queue together hold at most R·C entries

Both BFS and DFS have the same asymptotic bounds; the difference is traversal order, not total work.

Interactive Lab#

Both labs run on the same kind of board: a grid of open cells with roughly one in six turned into a wall, a green source and a red target dropped at random, and no adjacency list anywhere in sight. The neighbours are found by adding the four offsets and checking bounds, exactly as in the code above. A fresh board is generated each time the page loads, so the specific layout differs; what does not differ is the order in which the two strategies colour it in.

Let's take that board and run BFS on it. The queue makes the frontier advance as a wavefront: every cell at distance d from the source is coloured before any cell at distance d + 1, and walls simply fail the passability check and are skipped. Watch it stop the moment the target is dequeued, then trace the amber path back through the parent map. Because the target was first reached on the wavefront, that path is a shortest one by construction, and no comparison of alternatives was ever needed.

Now the same board with a stack. DFS follows one corridor to its end before backing up, so the colouring races off in a single direction instead of spreading evenly. It will still find the target and still reconstruct a path, but that path is whatever route the dive happened to take, not the shortest one. What DFS is genuinely better at is the flood-fill question: one launch from a cell visits its entire connected region, which is exactly what "count the islands" needs.

What to Remember#

  • Grid = implicit graph. Every cell is a node; its 4 (or 8) in-bounds neighbors are its edges. No explicit adjacency structure is needed.
  • Bounds + visited checks are mandatory. Always validate 0 <= nr < rows and 0 <= nc < cols, reject walls, and skip already-visited cells to avoid index errors and infinite loops.
  • BFS for shortest path. Because BFS explores in distance order, the first time it reaches a cell is via the minimum number of steps. Use it whenever a problem asks for "fewest moves," "shortest path," or "minimum distance."
  • DFS for flood fill and connected regions. Launching a DFS/BFS from each unvisited land cell and counting the launches gives the number of connected components. It's the canonical approach to "number of islands" and similar problems.
  • Mark visited on enqueue, not on dequeue. Adding a cell to seen when it enters the queue prevents the same cell from being enqueued multiple times by different neighbors, keeping the O(R·C) bound tight.