The disjoint set class - Data Structures and Problem Solving Using Java - page 896

figure 24.1
A 50 × 88 maze

and the ending point is the bottom-right corner. We can view the maze as a
50 × 88 rectangle of cells in which the top-left cell is connected to the bottom-
right cell, and cells are separated from their neighboring cells via walls.
A simple algorithm to generate the maze is to start with walls everywhere
(except for the entrance and exit). We then continually choose a wall ran-
domly and knock it down if the cells that the wall separates are not already
connected to each other. If we repeat this process until the starting and ending
cells are connected, we have a maze. Continuing to knock down walls until
every cell is reachable from every other cell is actually better because doing
so generates more false leads in the maze.
We illustrate the algorithm with a 5 × 5 maze, and Figure 24.2 shows the
initial configuration. We use the union/find data structure to represent sets of
cells that are connected to each other. Initially, walls are everywhere, and each
cell is in its own equivalence class.
Figure 24.3 shows a later stage of the algorithm, after a few walls have
been knocked down. Suppose, at this stage, that we randomly target the wall
that connects cells 8 and 13. Because 8 and 13 are already connected (they
are in the same set), we would not remove the wall because to do so would
simply trivialize the maze. Suppose that we randomly target cells 18 and 13
next. By performing two find operations, we determine that these cells are
in different sets; thus 18 and 13 are not already connected. Therefore we
knock down the wall that separates them, as shown in Figure 24.4. As a