Disjoint-set data structure: Difference between revisions

Revision as of 22:42, 22 August 2005

Revision as of 03:33, 23 August 2005

Line 1:

Given a 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 keeps track of such a partitioning. A '''union-find algorithm''' ([[Union-Find]]) is an algorithm that performs two useful 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.