# Disjoint Subgraphs Data Structure

(Redirected from Disjoint-Sets Data Structure)

Jump to navigation
Jump to search
A Disjoint Subgraphs Data Structure is a set of sets data structure that can represent a set of disjoint graphs.

**Context:**- It can (typically) support a Subset Find Operation.
- It can (typically) support a Subset Union Operation.
- …

**Counter-Example(s):****See:**Partition of a Set, Disjoint Sets, Singleton (Mathematics), Partitioning Problem.

## References

### 2014

- (Wikipedia, 2014) ⇒ http://en.wikipedia.org/wiki/Disjoint-set_data_structure Retrieved:2014-4-21.
- In computing, a
**disjoint-set data structure**is a data structure that keeps track of a set of elements partitioned into a number of disjoint (nonoverlapping) subsets. A union–find algorithm is an algorithm that performs two useful operations on such a data structure:*Find*: Determine which subset a particular element is in. This can be used for determining if two elements are in the same subset.*Union*: Join two subsets into a single subset.

- Because it supports these two operations, a disjoint-set data structure is sometimes called a
*union–find data structure*or*merge–find set*. The other important operation,*MakeSet*, which makes a set 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).In order to define these operations more precisely, some way of representing the sets is needed. One common approach is to select a fixed element of each set, called its

*representative*, to represent the set as a whole. Then,*Find*(x) returns the representative of the set that*x*belongs to, and*Union*takes two set representatives as its arguments.

- In computing, a