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 >= 0andnew_row < grid_height? - Is
new_col >= 0andnew_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.