Maze Generation: DFS, Prim, Kruskal & Wilson

A maze is a spanning tree of a grid graph

Treat every cell of a grid as a node and every possible wall between two adjacent cells as a potential edge. A perfect maze — exactly one path between any two cells, no loops, no isolated regions — is exactly a spanning tree of that grid graph: a subset of edges connecting every node with no cycles. Every one of the classic maze-generation algorithms is, underneath a different name, a spanning-tree algorithm applied to a grid, which is why they can look so different visually while all guaranteeing the same structural property.

DFS Backtracker: long, winding corridors

The depth-first search backtracker starts at a random cell, and repeatedly moves to a random unvisited neighbour, knocking down the wall between them, pushing the old cell onto a stack. When a cell has no unvisited neighbours, it pops the stack and continues from there.

stack = [startCell]; mark startCell visited
while stack not empty:
  current = stack.top
  neighbours = unvisited neighbours of current
  if neighbours empty: stack.pop(); continue
  next = random(neighbours)
  removeWall(current, next); mark next visited
  stack.push(next)

Because it always commits to depth before backing up, DFS tends to produce mazes with long, winding, low-branching corridors and comparatively few dead ends near the entrance — visually the most "maze-like" of the four to a human eye.

Prim's and Kruskal's: minimum spanning trees with random weights

Randomised Prim starts from one cell, keeps a frontier set of walls adjacent to the growing maze, and repeatedly picks a random wall from that frontier, carving it if it connects a visited cell to an unvisited one — structurally identical to the classic Prim minimum-spanning-tree algorithm with edge weights assigned randomly instead of by actual distance. Randomised Kruskal instead shuffles every wall in the grid into one random order and processes them one at a time, carving a wall whenever the two cells it separates belong to different already-connected components (tracked with a union-find / disjoint-set structure), and skipping it otherwise. Both guarantee a valid spanning tree by construction; their visual signature is shorter, more uniformly distributed dead ends and more frequent branching than DFS, because neither algorithm commits to extending one path as far as possible before backtracking.

Kruskal (randomised):
  edges = shuffle(all possible walls)
  dsu = new DisjointSet(allCells)
  for wall in edges:
    if dsu.find(wall.cellA) != dsu.find(wall.cellB):
      removeWall(wall); dsu.union(wall.cellA, wall.cellB)

Wilson: uniform spanning trees via loop-erased walks

DFS, Prim and Kruskal all produce a valid spanning tree, but not with the same probability for every possible spanning tree of the grid — some tree shapes are more likely to come out than others. The Wilson algorithm (1996) is the one exception on this page: it generates a spanning tree uniformly at random from the set of all possible spanning trees, using loop-erased random walks. Starting from an unvisited cell, it performs a random walk until it hits the growing maze, then erases any loop the walk crossed back over itself and adds the resulting loop-free path to the maze; repeated over all remaining unvisited cells, this produces a genuinely uniform sample — a mathematically stronger guarantee than the other three algorithms provide, at the cost of a much less predictable running time, since a random walk can wander for a long time before it happens to hit the maze.

Solving instantly with BFS

Because a perfect maze is a tree, there is exactly one path between the entrance and the exit, and breadth-first search finds it in O(cells) time by expanding outward one ring of distance at a time from the start and recording each cell's parent the first time it is reached, then walking backward from the exit through those parent pointers to reconstruct the path. BFS is the right choice here specifically because a tree has no cycles to worry about and no edge weights to compare, which is exactly the situation Dijkstra's algorithm and A* are built to handle at extra cost that buys nothing on a maze.

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.