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

equivalence class. This information provides the strategy to solve the equiva-
lence problem.
The input is initially a collection of N sets, each with one element. In this
initial representation all relations (except reflexive relations) are false. Each
set has a different element, so and such sets (in which any two
sets contain no common elements) are called disjoint sets.

S i S j ∩∅ =

The two basic disjoint set class operations are find , which returns the
name of the set (i.e., the equivalence class) containing a given element, and
the union , which adds relations. If we want to add the pair ( a, b ) to the list of
relations, we first determine whether a and b are already related. We do so by
performing find operations on both a and b and finding out whether they are
in the same equivalence class; if they are not, we apply union . This operation
merges the two equivalence classes containing a and b into a new equivalence
class. In terms of sets the result is a new set , which we create by
simultaneously destroying the originals and preserving the disjointedness of
all the sets. The data structure to do this is often called the disjoint set union/
find data structure. The union/find algorithm is executed by processing union/
find requests within the disjoint set data structure.

The two basic
disjoint set class
operations are
union and find .

S k = S i ∪ S j

The algorithm is dynamic because, during the course of algorithm execu-
tion, the sets can change via the union operation. The algorithm must also
operate as an online algorithm so that, when a find is performed, an answer
must be given before the next query can be viewed. Another possibility is an
off line algorithm in which the entire sequence of union and find requests are
made visible. The answer it provides for each find must still be consistent
with all the union s performed before the find . However, the algorithm can give
all its answers after it has dealt with all the questions. This distinction is simi-
lar to the difference between taking a written exam (which is generally off line
because you only have to give the answers before time expires) and taking an
oral exam (which is online because you must answer the current question
before proceeding to the next question).

In an online algo-
rithm , an answer
must be provided
for each query
before the next
query can be
viewed.

Note that we do not perform any operations to compare the relative values
of elements but merely require knowledge of their location. For this reason,
we can assume that all elements have been numbered sequentially, starting
from 0, and that the numbering can be determined easily by some hashing
scheme.
Before describing how to implement the union and find operations, we
provide three applications of the data structure.

The set elements
are numbered
sequentially, start-
ing from 0.

24.2.1 application: generating mazes

An example of the use of the union/find data structure is to generate mazes,
such as the one shown in Figure 24.1. The starting point is the top-left corner,