BFS and DFS on Grids

Terminology

Term	Definition
Grid graph	A 2D matrix treated as a graph where each cell is a node and edges connect adjacent cells (up, down, left, right).
BFS (breadth-first search)	Explores all neighbors at the current depth before moving deeper. Uses a queue. Guarantees shortest path in unweighted grids.
DFS (depth-first search)	Explores as deep as possible along each branch before backtracking. Uses a stack (or recursion). Good for connected component discovery.
4-directional	Movement restricted to up, down, left, right. The standard for most grid problems.
8-directional	Movement includes diagonals in addition to the 4 cardinal directions. Used in problems like "number of islands" with diagonal connectivity.
Flood fill	Starting from a seed cell, change all connected cells of the same color to a new color. The "paint bucket" tool in image editors.
Connected component	A maximal set of cells that are all reachable from each other through adjacent traversal. Each island is a connected component.
Visited matrix	A boolean grid tracking which cells have been explored, preventing infinite loops. Can also be done by modifying the grid in-place.

What & Why

Many coding problems present a 2D grid and ask you to explore it: count islands, find the shortest path through a maze, or fill a region with a new color. These are all graph traversal problems in disguise, where each cell is a node and edges connect adjacent cells.

BFS is the right choice when you need the shortest path in an unweighted grid, because it explores cells layer by layer (distance 1, then distance 2, etc.). DFS is simpler to implement recursively and works well for problems that just need reachability or connected component counting (like "number of islands").

The key implementation details are: choosing a direction array (4 or 8 directions), bounds checking, and marking cells as visited to avoid revisiting them. Most grid problems follow a nearly identical template, making this one of the most reusable patterns.

How It Works

DFS: Island Counting

Scan the grid. When you find an unvisited land cell, start a DFS to mark the entire island as visited. Each DFS call counts one island.

BFS: Shortest Path in a Maze

Use BFS from the start cell. Each layer of the BFS corresponds to one step. The first time you reach the target cell, you have the shortest path.

Complexity Analysis

Problem	Time	Space
Number of islands (DFS)	$O(m \times n)$	$O(m \times n)$ recursion stack worst case
Flood fill (BFS/DFS)	$O(m \times n)$	$O(m \times n)$
Shortest path (BFS)	$O(m \times n)$	$O(m \times n)$
Multi-source BFS	$O(m \times n)$	$O(m \times n)$

Every cell is visited at most once. For an $m \times n$ grid with 4-directional movement, each cell checks 4 neighbors:

$T = O(m \times n), \quad S = O(m \times n)$

Implementation

Number of Islands (DFS)

ALGORITHM CountIslands(grid, m, n)
  INPUT: m x n grid of 0s and 1s
  OUTPUT: number of islands

  count = 0
  directions = [(-1,0), (1,0), (0,-1), (0,1)]

  FUNCTION DFS(r, c)
    IF r < 0 OR r >= m OR c < 0 OR c >= n THEN RETURN
    IF grid[r][c] != 1 THEN RETURN

    grid[r][c] = 0    // mark visited

    FOR EACH (dr, dc) IN directions DO
      DFS(r + dr, c + dc)
    END FOR
  END FUNCTION

  FOR r = 0 TO m - 1 DO
    FOR c = 0 TO n - 1 DO
      IF grid[r][c] = 1 THEN
        count = count + 1
        DFS(r, c)
      END IF
    END FOR
  END FOR

  RETURN count
END

Shortest Path in Maze (BFS)

ALGORITHM ShortestPath(grid, m, n, start, end)
  INPUT: m x n grid (0 = open, 1 = wall), start and end coordinates
  OUTPUT: shortest path length, or -1 if unreachable

  IF grid[start.r][start.c] = 1 OR grid[end.r][end.c] = 1 THEN
    RETURN -1
  END IF

  queue = empty queue
  queue.enqueue((start.r, start.c, 0))
  visited = m x n boolean matrix, all FALSE
  visited[start.r][start.c] = TRUE
  directions = [(-1,0), (1,0), (0,-1), (0,1)]

  WHILE queue is not empty DO
    (r, c, dist) = queue.dequeue()

    IF r = end.r AND c = end.c THEN
      RETURN dist
    END IF

    FOR EACH (dr, dc) IN directions DO
      nr = r + dr
      nc = c + dc
      IF nr >= 0 AND nr < m AND nc >= 0 AND nc < n
         AND grid[nr][nc] = 0 AND NOT visited[nr][nc] THEN
        visited[nr][nc] = TRUE
        queue.enqueue((nr, nc, dist + 1))
      END IF
    END FOR
  END WHILE

  RETURN -1
END

Flood Fill

ALGORITHM FloodFill(grid, m, n, sr, sc, newColor)
  INPUT: m x n grid, start row sr, start col sc, newColor
  OUTPUT: grid with connected region recolored

  oldColor = grid[sr][sc]
  IF oldColor = newColor THEN RETURN grid

  FUNCTION DFS(r, c)
    IF r < 0 OR r >= m OR c < 0 OR c >= n THEN RETURN
    IF grid[r][c] != oldColor THEN RETURN

    grid[r][c] = newColor

    DFS(r - 1, c)
    DFS(r + 1, c)
    DFS(r, c - 1)
    DFS(r, c + 1)
  END FUNCTION

  DFS(sr, sc)
  RETURN grid
END

Real-World Applications

Image processing: flood fill is the algorithm behind the paint bucket tool in Photoshop and GIMP. Connected component labeling segments objects in images.
Game pathfinding: BFS on tile-based grids finds shortest paths for NPCs in strategy games and roguelikes.
Geographic information systems: counting connected land masses, computing watershed boundaries, and flood simulation all use grid BFS/DFS.
Circuit board routing: Lee's algorithm uses BFS on a grid to find shortest wire routes between pins on a PCB.
Robot navigation: occupancy grids represent the environment as a 2D matrix, and BFS plans collision-free paths.

Key Takeaways

Grid problems are graph problems: each cell is a node, edges connect adjacent cells, and BFS/DFS are the standard traversal tools
Use BFS when you need shortest path (unweighted), use DFS when you need reachability or connected component counting
The direction array pattern (4-directional or 8-directional) keeps the code clean and easy to modify
Mark cells as visited either with a separate boolean matrix or by modifying the grid in-place (setting land to water)
Watch for stack overflow with recursive DFS on large grids: iterative DFS with an explicit stack avoids this