Maze Generation Algorithms: Spanning Trees and Graph Theory

A maze is a spanning tree in disguise

Take a grid of cells and treat every pair of adjacent cells as a potential edge, with a wall in between them by default. A perfect maze — exactly one path between any two cells, no loops, nothing unreachable — is exactly what graph theorists call a spanning tree of that grid graph: a subset of edges (walls knocked down) that connects every cell using exactly n − 1 edges, with no cycles. Every maze-generation algorithm on this simulation is, underneath, an algorithm for building a random spanning tree; they differ only in which spanning tree they tend to produce.

grid graph:   n cells, up to 2n edges (shared walls)
perfect maze: a spanning tree — exactly n−1 edges kept, zero cycles, fully connected

Same goal, very different textures

Recursive backtracking (randomised depth-first search) carves a corridor forward until it dead-ends, then backtracks and tries a different unvisited direction. Because it commits to long runs before backtracking, it produces mazes with long, winding corridors and comparatively few branch points — a “river” texture. Randomised Prim’s algorithm instead grows the maze outward from a frontier of candidate walls, picking one at random each step; because it isn’t committed to any single direction, it produces shorter dead ends and a denser, more uniformly branching texture. Both algorithms are correct — both always terminate in a valid spanning tree — but they sample from very different, structurally biased subsets of all possible spanning trees.

Wilson's algorithm: sampling without bias

Wilson’s algorithm takes a different, cleverer approach specifically to remove that bias. It performs a loop-erased random walk: start a random walk from an unvisited cell, and whenever the walk revisits a cell it has already stepped on, erase the resulting loop before continuing. Chained repeatedly until every cell has joined the tree, this procedure is mathematically proven to produce a uniform spanning tree — every possible spanning tree of the grid is equally likely to come out, something neither the backtracker nor Prim’s algorithm can claim. The cost is variance in running time: early loop-erased walks on a mostly-empty grid can wander for a while before making progress.

Kruskal's algorithm and union-find

Kruskal’s algorithm shuffles every candidate wall into a random order, then processes them one at a time: knock a wall down only if the two cells it separates aren’t already connected by some other path through the maze so far. Checking “already connected” efficiently is exactly the job of a union-find (disjoint-set) data structure, which tracks connected components and can merge or query them in almost constant time — the same data structure used for Kruskal’s minimum-spanning-tree algorithm in a general graph.

shuffle(walls)
for (a, b) in walls:
  if find(a) != find(b):     // not already connected
    remove_wall(a, b)
    union(a, b)               // merge their components

Solving is almost too easy

Because a perfect maze is a tree, there is exactly one path between the entrance and the exit — there is no shortest-path problem to solve, only a single path to find. Breadth-first search from the start still does the job cleanly: it explores outward one layer at a time, and following parent pointers back from the goal once it’s reached reconstructs that one true path. BFS earns its keep mainly on imperfect mazes with loops added back in, where multiple paths genuinely compete and only BFS (or Dijkstra, for weighted variants) is guaranteed to find the shortest one.

Frequently asked questions

Try it live

Everything above runs in your browser — open Maze Generator and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.