In this assignment you will use a disjoint set forest to build a maze. Your maze should contain a collection of cells separated by walls in such a way that there is exactly one simple path (that is, a path that does not visit any cell more than once) separating any two cells.
To build a maze, you must do the following. Let M be the number of rows and and N be the number of columns of your square maze. When all walls are present (see gure), each of the M N cells in the maze belongs to a di erent set. Thus you have M N sets in your disjoint set forest. When you remove a wall, if the cells that were separated by that wall belonged to di erent sets, you must unite these sets. This process is repeated until all cells belong to a single set; at that point you display the maze. The following pseudocode illustrates the process to build the maze:
Create full maze with all adjacent cells are separated by a wall Assign each cell to a different set in a disjoint set forest S While S has more than one set
Select a random wall w =[c1,c2]
If cells c1 and c2 belong to different sets, remove w and join c1’s set and c2’s set otherwise do nothing
Display maze
Initial maze, including cell numbers Maze after removing randomly-chosen walls
The program maze.py, provided in the class web page, contains code for all drawing operations and to remove randomly chosen walls from the maze. You will need to modify the program to remove the walls that will result in a correct maze.
Perform a comparison of running times of the program using standard union and union by size with path compression for various maze sizes. As usual, write a report describing your work.
