Maze Generation

This shows a maze being generated with Kruskal's algorithm. Essentially, it works like this: initially, every cell in the maze is walled off from its neighbors, and every cell is in its own "group" or set. At each step, we randomly pick a wall, and if the cells connected by that wall are in different groups, we remove that wall and join them into the same group. Kruskal's algorithm is a graph algorithm which generates minimum spanning trees, so we end up with a tree at the end of this process. In other words, we end up with a maze! The reason for using Kruskal's algorithm over say Prim's is that, when we use a special data structure called the "Disjoint-set" data structure, we can keep track of our cell groupings very efficiently. Notice that, we visit each wall exactly once, and decide if the wall is kept or removed. Each decision takes (effectively) a constant amount of time. So our algorithm runs linearly with the number of walls!