Breadth-First Search (BFS) is a graph traversal algorithm that explores all nodes at the current distance before moving deeper. Picture dropping a pebble in water — waves ripple outward evenly in every direction. That's exactly how BFS spreads through a maze, making it the go-to algorithm when you need the shortest path.
When you need the optimal route through a maze where every step costs the same, BFS is your best bet. Unlike DFS, which may wander down long corridors, BFS systematically finds the shortest solution. This makes it the benchmark for evaluating maze complexity.
Game developers use BFS to measure how hard a maze is. The BFS solution length divided by the maze dimensions gives a "difficulty ratio." A higher ratio means more twisting, more wrong turns, and a harder puzzle. Our Classic Maze uses this metric to calibrate difficulty levels.
| Time Complexity | O(V + E) — visits each vertex and edge once |
| Space Complexity | O(V) — stores the entire frontier in a queue |
| Finds Shortest Path? | ✅ Yes (unweighted graphs) |
| Complete? | ✅ Yes |
| Data Structure | Queue (FIFO) |
| Best For | Shortest path in unweighted mazes, maze difficulty evaluation |
Our maze solver uses BFS to show you the optimal path. Play a maze, then activate the solver to see BFS in action as it discovers the shortest route.
Yes — in unweighted mazes where every step costs the same. For weighted mazes, use Dijkstra's or A*.
BFS stores the entire frontier (all cells at the current distance) in a queue. In a wide-open area this can be huge. DFS only stores the current path, which is typically much smaller.
Rarely on its own. BFS-based generation produces mazes with very short dead ends and a "bushy" structure. Most generators prefer recursive backtracking or Prim's algorithm.