75x50 Maze generated by a Kruskal's algorithm (Top-Left flooding).

Flooding starting from Top-Left corner

The tree representing its data structure topology from Top-Left corner.

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).

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

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;
} 

Mazes generated tend to have a lot of very short dead-ends, 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.

1. Select an edge at random.

2. Both cells are on their own bucket (not connected from any path):
Connect them and merge their buckets.

3. After few iterations...

4. After few more iterations, the edge selected concern two cells connected to the same path (same bucket):
The edge is simply thrown away (cf. next slide).

5. Another edge is selected.

6. After few more iterations.

7. All edge are processed (all buckets are merge to a unique one): Maze is done!