Breadth-First and Depth-First Search

00:000 Start

New Maze Free DFS Show Labels Export Maze

Possible Path Shortest Path

Suppose you need to find your way out of the maze above, starting from where the turtle is. How can you connect your knowledge of graphs to the maze problem? What are the nodes? What are the edges? Furthermore, how would you use graphs to answer the following questions:

1. How would you find a path out of the maze?
2. How would you find the shortest path out of the maze?
3. How would you ensure you visit all locations in the maze (to collect all the leaves)?
4. How would you build a maze in the first place?

Try using the arrow keys below to navigate through the maze and, ultimately, escape. If you reach the outlet, the turtle will be frozen, so you can click on the "New Maze" button to play again. The number of squares in each direction can be controlled by the spinbox number input.

After covering depth-first-search, set the mode to "DFS" using the dropdown. Come up with a strategy and then click "Start"!