Java Reference
In-Depth Information
spond to the connected components. Another application for UNION/FIND occurs
in Kruskal's algorithm for computing the minimal cost spanning tree for a graph
(Section 11.5.2).
The input to the UNION/FIND algorithm is typically a series of equivalence
pairs. In the case of the connected components example, the equivalence pairs
would simply be the set of edges in the graph. An equivalence pair might say that
object C is equivalent to object A. If so, C and A are placed in the same subset. If
a later equivalence relates A and B, then by implication C is also equivalent to B.
Thus, an equivalence pair may cause two subsets to merge, each of which contains
several objects.
Equivalence classes can be managed efficiently with the UNION/FIND alg-
orithm. Initially, each object is at the root of its own tree. An equivalence pair is
processed by checking to see if both objects of the pair are in the same tree us-
ing method
differ
. If they are in the same tree, then no change need be made
because the objects are already in the same equivalence class. Otherwise, the two
equivalence classes should be merged by the
UNION
method.
Example6.2
As an example of solving the equivalence class problem,
consider the graph of Figure 6.6. Initially, we assume that each node of the
graph is in a distinct equivalence class. This is represented by storing each
as the root of its own tree. Figure 6.7(a) shows this initial configuration
using the parent pointer array representation. Now, consider what happens
when equivalence relationship (A, B) is processed. The root of the tree
containing A is A, and the root of the tree containing B is B. To make them
equivalent, one of these two roots is set to be the parent of the other. In
this case it is irrelevant which points to which, so we arbitrarily select the
first in alphabetical order to be the root. This is represented in the parent
pointer array by setting the parent field of B (the node in array position 1
of the array) to store a pointer to A. Equivalence pairs (C, H), (G, F), and
(D, E) are processed in similar fashion. When processing the equivalence
pair (I, F), because I and F are both their own roots, I is set to point to F.
Note that this also makes G equivalent to I. The result of processing these
five equivalences is shown in Figure 6.7(b).
The parent pointer representation places no limit on the number of nodes that
can share a parent. To make equivalence processing as efficient as possible, the
distance from each node to the root of its respective tree should be as small as
possible. Thus, we would like to keep the height of the trees small when merging
two equivalence classes together. Ideally, each tree would have all nodes pointing
directly to the root. Achieving this goal all the time would require too much ad-
