188 CHAPTER 3 Relations
Application: UNION-FIND
The UNION-FIND algorithm has a set of elements X and a relation R defined on X as
its input. The UNION-FIND algorithm starts with a partition of X in which each element
is a set consisting of a single element of X. Each related pair of elements is processed as
follows: If a related pair of elements are in different elements of the partition, those two
sets of the partition are joined, forming a new partition of X with fewer elements. If the
two elements are already in the same element of the partition, nothing is done.
As an example of how the algorithm operates, Table 3.10 shows a set with six elements
that has a relation consisting of the pairs (0, 2), (1, 4), (2, 5), (3, 6), (0, 4), and (1, 2). The
final partition has two elements, {0, 1, 2, 4, 5} and 13, 61.Table 3.10 UNION-FIND AlgorithmNew Related Pair Current Partition Defined by the Equivalence Relation
0 101, {1}, {2}, 13], {4}, 151, {6}
Process 0 R 2 0 and 2 are in different elements of the partition
Form new partition {0, 2}, [1), 13), {4}, {5}, {6}
Process 1 R 4 1 and 4 are in different elements of the partition
Form new partition {0, 2}, {1, 4}, {3}, (51, (6)
Process 2 R 5 2 and 5 are in different elements of the partition
Form new partition {0, 2, 5}, [1, 4}, {3}, {6}
Process 3 R 6 3 and 6 are in different elements of the partition
Form new partition {0, 2, 5}, [1, 4), {3, 61
Process 0 R 4 0 and 4 are in different elements of the partition
Form new partition 10, 1, 2, 4, 51, {3, 61
Process 1 R 2 1 and 2 are in the same element of the partition
Leave partition as is {0, 1, 2, 4, 5], {3, 6}In computer science, this problem is of great interest, because it is an integral pro-
cessing step in many algorithms. As an example, consider using this algorithm to find
associations among a set of authors for a personal collection of journal articles about a
single topic. The problem is to determine which of these authors have worked together.
By starting with each author in a set by himself or herself, the articles will tell how to
join pairs or sets of authors into bigger sets because they have worked together. The final
outcome would be a partition of the authors such that two authors are in the same element
of the partition if and only if they had worked together. The problem of determining an
effective data structure for managing the information being processed is a major topic in
data structures.rnExercises
- Identify the equivalence classes of M for the following relations:
(a) (mod 4)
(b) (mod 6)