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

1 package weiss.nonstandard;
2
3 // DisjointSets class
4 //
5 // CONSTRUCTION: with int representing initial number of sets
6 //
7 // ******************PUBLIC OPERATIONS*********************
8 // void union( root1, root2 ) --> Merge two sets
9 // int find( x ) --> Return set containing x
10 // ******************ERRORS********************************
11 // Error checking or parameters is performed
12
13 public class DisjointSets
14 {
15 public DisjointSets( int numElements )
16 { /* Figure 24.21 */ }
17
18 public void union( int root1, int root2 )
19 { /* Figure 24.21 */ }
20
21 public int find( int x )
22 { /* Figure 24.21 */ }
23
24 private int [ ] s;
25
26
27 private void assertIsRoot( int root )
28 {
29 assertIsItem( root );
30 if( s[ root ] >= 0 )
31 throw new IllegalArgumentException( );
32 }
33
34 private void assertIsItem( int x )
35 {
36 if( x < 0 || x >= s.length )
37 throw new IllegalArgumentException( );
38 }
39 }

figure 24.20
The disjoint sets class
skeleton

In our routine, union is performed on the roots of the trees. Sometimes the
operation is implemented by passing any two elements and having union per-
form the find operation to determine the roots.
The interesting procedure is find . After the find has been performed
recursively, array[x] is set to the root and then is returned. Because this pro-
cedure is recursive, all nodes on the path have their entries set to the root.