Matrix & Grid Traversal — BFS and DFS on a Grid

The Concept

A 2D grid is an implicit graph. You never have to write out an adjacency list — 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). Reframing a grid as a graph immediately unlocks every graph algorithm you already know.

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 — making 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:

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) — cell plus 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.

Complexity Analysis

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

Interactive Lab

BFS explores the grid in rings outward from the start cell. Watch the frontier expand uniformly — every cell at distance d is colored before any cell at distance d + 1.

DFS follows one corridor to its end before backing up. This makes it ideal for flood fill: a single DFS from a cell visits its entire connected region in one call.

The pathfinder combines obstacle-aware BFS with path reconstruction. Notice how the shortest path is highlighted once the goal is reached.

Key Takeaways

• 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 — 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.