Editing Maze generation algorithm (section)

=== Iterative randomized Kruskal's algorithm (with sets) ===
[[File:KruskalGeneratedMaze.webm|thumb|An animation of generating a 30 by 20 maze using Kruskal's algorithm]]
This algorithm is a randomized version of [[Kruskal's algorithm]].

# Create a list of all walls, and create a set for each cell, each containing just that one cell.
# For each wall, in some random order:
## If the cells divided by this wall belong to distinct sets:
### Remove the current wall.
### Join the sets of the formerly divided cells.

There are several data structures that can be used to model the sets of cells.  An efficient implementation using a [[disjoint-set data structure]] can perform each union and find operation on two sets in nearly constant [[amortized time]] (specifically, <math>O(\alpha(V))</math> time; <math>\alpha(x) < 5</math> for any plausible value of <math>x</math>), so the running time of this algorithm is essentially proportional to the number of walls available to the maze.

It matters little whether the list of walls is initially randomized or if a wall is randomly chosen from a nonrandom list, either way is just as easy to code.

Because the effect of this algorithm is to produce a minimal spanning tree from a graph with equally weighted edges, it tends to produce regular patterns which are fairly easy to solve.