Course contentsShow
← Computer Science
Lesson 704 of 2,87217. Graph Traversal AlgorithmsFree lesson

BFS in Grid Graphs

Applying BFS to 2D grids: exploring 4 or 8 directions, boundary checking, and common grid problems.

BFS in Grid Graphs

What you'll learn: How to apply BFS to 2D grids by treating each cell as a node and exploring neighbors in 4 or 8 directions.

The Core Idea

Many real-world problems—like navigating mazes, finding shortest paths on maps, or solving puzzles—are represented as 2D grids. Each cell is essentially a graph vertex, and adjacent cells are connected by edges. BFS naturally extends to grids: instead of following explicit neighbor lists, you explore cells in the four cardinal directions (up, down, left, right) or all eight directions (including diagonals).

How It Works

Start BFS from a source cell, enqueuing it with its coordinates (row, col). When processing a cell, check all valid neighbors:

4-directional movement:

directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]  # right, left, down, up

8-directional movement (with diagonals):

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

For each direction, compute the neighbor's coordinates and check boundaries:

  • Is new_row >= 0 and new_row < grid_height?
  • Is new_col >= 0 and new_col < grid_width?
  • Is the cell unvisited and traversable (not a wall/obstacle)?

Use a visited set or mark cells in the grid itself to avoid revisiting.

Common Grid Problems

  • Shortest path in maze: BFS finds the minimum steps from start to exit
  • Flood fill: Paint connected regions (like paint bucket tool)
  • Distance from multiple sources: Multi-source BFS to find nearest exit/resource
  • Island counting: Though typically DFS, BFS works too

Key Takeaway: BFS on grids treats each cell as a vertex with neighbors in 4 or 8 directions; always validate boundaries and track visited cells to efficiently solve spatial problems.