Questions
27 of 59
How do you solve a Maze using Graph algorithms?
Difficulty: 3/10
Maze as a Graph
A maze can be modeled as a graph where each walkable cell is a vertex and an edge connects cells that can be reached directly. BFS finds the shortest path in an unweighted maze, while DFS can determine reachability or find any path. For weighted movement costs, algorithms such as Dijkstra may be required.
javascript
- 1
Walkable cells become graph vertices.
- 2
Adjacent walkable cells become edges.
- 3
BFS gives the shortest number-of-moves path.
- 4
DFS can find whether a path exists.
- 5
A* can accelerate target-directed pathfinding with a suitable heuristic.
Follow-up Questions
- Why is BFS preferable to DFS for shortest paths?
- When would A* be useful?