# Maze Generation Using Randomized Kruskal's Algorithm

25 May 2015

I previously posted a maze generator using depth-first search and backtracking. This implementation however uses a randomized version of Kruskal's Algorithm (Minimum Spanning Tree Algorithm).
The Wikipedia description of the algorithm does a far better job summarising it than I ever could:

*
*

- Create a list of all walls, and create a set for each cell, each containing just that one cell.
- For each wall, in some random order:
- If the cells divided by this wall belong to distinct sets:
- Remove the current wall.
- Join the sets of the formerly divided cells.

- If the cells divided by this wall belong to distinct sets:

For my implementation I stored a list of the edges (walls) between each cell and DisjointSets data structure to keep track of which cells are traversable. Simply, DisjointSets keeps track of a fixed number of disjoint sets (sets that do not overlap). Here initially each cell is a disjoint set. The sets can be unioned together as they need to be merged, i.e when a wall is destroyed between two sets of cells. As described above, I select random edges from my list to remove provided removing that edge will join two disjoint parts of the maze together until my DisjointSets contains a single set containing every cell. I assume the start and end points to be in the top-left and bottom-right positions of the maze respectively, but this is arbitrary as any cell can be reached from any other cell via some route. Below is the source code for my algorithm and DisjointSets data structure. Either generate() or animate() can be called depending on whether you want the drawing delay as the algorithm runs.