The Disjoint Set data structure will be used in the creation of a maze. The algorithm to do this is discussed in the textbook in chapter 8.

Write a program to generate and display a maze as described in the textbook. The program may either be a command-line program that generates a character-based maze, or it may be a GUI program that draws the maze in a window.

The user should be able to specify the number of rows and columns in the maze, at least up to 20x20. You must use the DisjSet class from the textbook (Data Structures and Algorithm Analysis in Java, by Mark Allen Weiss, 3rd edition; Page number: 352) to implement the textbook's algorithm. The DisjSet class must be used as given in the textbook without making modifications to it.

1 public class DisjSets

2 {

3 public DisjSets( int numElements )

4 { /* Figure 8.7 */ }

5 public void union( int root1, int root2 )

6 { /* Figures 8.8 and 8.14 */ }

7 public int find( int x )

8 { /* Figures 8.9 and 8.16 */ }

9

10 private int [ ] s;

11 }

Figure 8.6 Disjoint set class skeleton

1 /**

2 * Construct the disjoint sets object.

3 * @param numElements the initial number of disjoint sets.

4 */

5 public DisjSets( int numElements )

6 {

7 s = new int [ numElements ];

8 for( int i = 0; i < s.length; i++ )

9 s[ i ] = -1;

10 }

Figure 8.7 Disjoint set initialization routine

1 /**

2 * Union two disjoint sets.

3 * For simplicity, we assume root1 and root2 are distinct

4 * and represent set names.

5 * @param root1 the root of set 1.

6 * @param root2 the root of set 2.

7 */

8 public void union( int root1, int root2 )

9 {

10 s[ root2 ] = root1;

11 }

Figure 8.8 union (not the best way)

1 /**

2 * Perform a find.

3 * Error checks omitted again for simplicity.

4 * @param x the element being searched for.

5 * @return the set containing x.

6 */

7 public int find( int x )

8 {

9 if( s[ x ] < 0 )

10 return x;

11 else

12 return find( s[ x ] );

13 }

Figure 8.9 A simple disjoint set find algorithm

1 /**

2 * Union two disjoint sets using the height heuristic.

3 * For simplicity, we assume root1 and root2 are distinct

4 * and represent set names.

5 * @param root1 the root of set 1.

6 * @param root2 the root of set 2.

7 */

8 public void union( int root1, int root2 )

9 {

10 if( s[ root2 ] < s[ root1 ] ) // root2 is deeper

11 s[ root1 ] = root2; // Make root2 new root

12 else

13 {

14 if( s[ root1 ] == s[ root2 ] )

15 s[ root1 ]--; // Update height if same

16 s[ root2 ] = root1; // Make root1 new root

17 }

18 }

Figure 8.14 Code for union-by-height (rank)

1 /**

2 * Perform a find with path compression.

3 * Error checks omitted again for simplicity.

4 * @param x the element being searched for.

5 * @return the set containing x.

6 */

7 public int find( int x )

8 {

9 if( s[ x ] < 0 )

10 return x;

11 else

12 return s[ x ] = find( s[ x ] );

13 }

Figure 8.16 Code for the disjoint set find with path compression

8.7 An Application

An example of the use of the union/find data structure is the generation of mazes, such

as the one shown in Figure 8.25. In Figure 8.25, the starting point is the top-left corner,

and the ending point is the bottom-right corner. We can view the maze as a 50-by-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 randomly, 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, then we have a maze. It is actually

There is no more information to provide!!!