Problem:
A maze can be modeled using an undirected graph by having a vertex for a starting point, a finishing point, dead ends, and locations in the maze where more than one path can be chosen, and then connecting the vertices according to the paths in the maze.
(a) Construct a graph for the maze shown above.
(b) Imagine you were lost in a maze and had access to a graph traversal algorithm to help you get out of it. Which algorithm would be more useful, DFS or BFS? Justify your answer. (Note that the maze could be very large and the corresponding graph could have a very large number of nodes.)
A maze can be modeled using an undirected graph by having a vertex for a starting point, a finishing point, dead ends, and locations in the maze where more than one path can be chosen, and then connecting the vertices according to the paths in the maze.
(a) Construct a graph for the maze shown above.
(b) Imagine you were lost in a maze and had access to a graph traversal algorithm to help you get out of it. Which algorithm would be more useful, DFS or BFS? Justify your answer. (Note that the maze could be very large and the corresponding graph could have a very large number of nodes.)
Solution:
(a). A maze can be represented as a graph. In order to do so we must consider the Junctions of the maze as the vertices in a graph. We can connect both the vertices if there is a way from one junction to another junction. This approach will build an path from start to end which will help in solving the maze.
(a). A maze can be represented as a graph. In order to do so we must consider the Junctions of the maze as the vertices in a graph. We can connect both the vertices if there is a way from one junction to another junction. This approach will build an path from start to end which will help in solving the maze.
The squares in the above diagram represent the junction points.
Now let us construct a graph out of the above diagram. For convenience I will be naming each junction.
Here ‘S’ stands for Start and ‘F’ stands for Finish. X,Y,Z,W,M,S,T,U,V represent vertices of dead ends.
(B). First let us have a look at how BFS and DFS solve the maze problem.
DFS :
➔ Depth First Search is a pretty good recursive search algorithm, it always takes the rightmost approach and if it encounters a dead end then it will backtrack until the first place it can go left or straight.
➔ The problem with DFS is that it takes a lot of space while solving the maze, the reason behind this is that for DFS you may have to keep the complete track in memory. When the maze is very large this can be an issue for using DFS to solve the maze.
➔ DFS will always find a solution in case of closed mazes, whereas in the case of open mazes DFS may go into infinite loop.
➔ For mazes with more than one solutions DFS does not always return the shortest path.
BFS :
➔ By definition Breadth first search will first check for all possible paths at a particular depth before moving to lower depth. So if a solution exists with length 10, BFS will find it before trying any solutions of depth 11.
➔ Contrary to DFS BFS does not have the issue with space since it does not need the complete track to be in memory. Also BFS can solve open mazes without going into a infinite loop.
➔ For mazes with more than one solutions BFS always returns the shortest path.
Conclusion:
When it comes to time complexity both BFS and DFS are pretty similar, I would go with BFS for solving mazes because it is better in terms of space complexity when compared with DFS. Also BFS will definitely return a solution in case of open maze whereas DFS may go into a infinite loop.
(B). First let us have a look at how BFS and DFS solve the maze problem.
DFS :
➔ Depth First Search is a pretty good recursive search algorithm, it always takes the rightmost approach and if it encounters a dead end then it will backtrack until the first place it can go left or straight.
➔ The problem with DFS is that it takes a lot of space while solving the maze, the reason behind this is that for DFS you may have to keep the complete track in memory. When the maze is very large this can be an issue for using DFS to solve the maze.
➔ DFS will always find a solution in case of closed mazes, whereas in the case of open mazes DFS may go into infinite loop.
➔ For mazes with more than one solutions DFS does not always return the shortest path.
BFS :
➔ By definition Breadth first search will first check for all possible paths at a particular depth before moving to lower depth. So if a solution exists with length 10, BFS will find it before trying any solutions of depth 11.
➔ Contrary to DFS BFS does not have the issue with space since it does not need the complete track to be in memory. Also BFS can solve open mazes without going into a infinite loop.
➔ For mazes with more than one solutions BFS always returns the shortest path.
Conclusion:
When it comes to time complexity both BFS and DFS are pretty similar, I would go with BFS for solving mazes because it is better in terms of space complexity when compared with DFS. Also BFS will definitely return a solution in case of open maze whereas DFS may go into a infinite loop.