Quick Access
Description
Kruskal's Maze Generator is a randomized version of Kruskal’s algorithm: a method for producing a minimal spanning tree for a weighted graph.
Kruskal's is interesting because it does not "grow" the Maze like a tree, but instead carves passage segments all over the Maze at random, making it very fun to watch. Still, it results in a perfect Maze in the end.
The counterpart is to require storage proportional to the size of the Maze, along with the ability to enumerate each edge between cells in random order (Using here a set of edges and taking them randomly).
How To Build
Once we have all of the edges into a big set and a unique subset id associated to each cell; all we need is to pick an edge at random, check if the adjacent cells belong to a different subset and unify them by setting the same id for all cells of both subsets.
Steps
Kruskal's Original Version  Maze Generator Version  



The randomized algorithm changes the first loop step so that instead of pulling out the edge with the lowest weight, you remove an edge from the set at random.
Code
Maze KruskalS(int width, int height) { Maze maze(width, height); // Create a set with all connecting edges // Create a vector of buckets for each cell with their id. Set edges(maze); // #edges = (height  1) * width + (width  1) * height BucketsVector bucketCells(maze); // #buckets = #cells = height * width // While the set of edges is not empty while (!edges.empty()) { // Randomly get an edge and remove it from the set auto edge = GetRandom(edges); // If cells are not already in the same bucket: Connect them and Merge Buckets if (BucketId(edge.first) != BucketId(edge.second)) { Connect(edge.first, edge.second); MergeBuckets(bucketCells, edge); } } return maze; }
Texture
Mazes generated tend to have a lot of very short deadends, giving the maze a kind of "spiky" look. This algorithm yields Mazes with a low "River" factor, but not as low as Prim's algorithm.