In computing, given a set of elements, it is often useful to break them up or partition them into a number of separate, nonoverlapping sets. A disjoint-set data structure is a data structure that keeps track of such a partitioning. A union-find algorithm is an algorithm that performs two useful operations on such a data structure:
- Find: Determine which set a particular element is in. Also useful for determining if two elements are in the same set.
- Union: Combine or merge two sets into a single set.
The Union-Find algorithm is used for maintaining
a number of non-overlapping sets from a finite universe of
elements. The algorithm has applications in a number of areas
including the computation of spanning trees, in image processing,
as well as in scientific computations.
Although the algorithm is inherently sequential there has been
some previous efforts at constructing parallel implementations.
These have mainly focused on shared memory computers.
By REX LOUIE B PILONGO
