Disjoint-set data structure: Difference between revisions

Revision as of 10:00, 4 October 2004

Revision as of 19:56, 4 October 2004

Line 1:

InGiven [[computera science]]set of elements, it is often useful to break them up or partition them into a number of separate, nonoverlapping groups. A '''disjoint-set data structure''' is a [[data structure]] that assignskeeps eachtrack elementof insuch a set to one of a number of groups of elementspartitioning. A '''union-find algorithm''' is aan wayalgorithm ofthat performingperforms two criticaluseful operations on such a data structure:

* '''Find''': Determine which group a particular element is in. Also useful for determining if two elements are in the same group.

* '''Union''': Combine or merge two groups into a single group.

The other important operation, '''MakeSet''', which makes a singleton setgroup containing only a given element (a [[singleton]]), is generally trivial. With these three operations, many practical partitioning problems can be solved (see the ''Applications'' section).

While we could represent the sets themselves as objects and have the operations operate on these sets, the more common approach is to choose an element from each set as a ''representative''; then, '''Find''' returns the representative of the set that the given element is in, and '''Union''' takes the representatives of two given sets.