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.