Time Complexity
O(rows × cols)
This algorithm uses Breadth-First Search to find the shortest path through a maze from start to finish, navigating around walls.
How it works:
1. Start BFS from the starting cell
2. Explore all 4 neighbors (up, down, left, right)
3. Skip walls and already-visited cells
4. Mark each explored cell and record its parent
5. When the end is reached, trace back through parents to find the path
Time Complexity: O(rows × cols)
Space Complexity: O(rows × cols)
Properties:
- Guarantees the shortest path
- Explores level by level (nearest cells first)
- Works on unweighted grids
BFS-based pathfinding is fundamental in game development, robotics, and navigation systems. For weighted grids, Dijkstra's or A* would be used instead.
Related algorithms
Frequently asked questions
- What is Maze Pathfinding (BFS)?
- This algorithm uses Breadth-First Search to find the shortest path through a maze from start to finish, navigating around walls.
- What is the complexity of Maze Pathfinding (BFS)?
- Time (average): O(rows × cols) · Space: O(rows × cols)
- Who is this Maze Pathfinding (BFS) visualizer for?
- The Maze Pathfinding (BFS) visualization targets intermediate-level learners in the Backtracking category. Useful for students, interview prep, and hands-on review.
- What algorithms are related to Maze Pathfinding (BFS)?
- In the same category (Backtracking) you can explore: N-Queens Problem, Sudoku Solver. Each has an interactive visualization.