Disjoint Subgraphs Data Structure

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):
  • an Overlapping-Sets Data Structure.
  • Partition Refinement Data Structure.
• See: Partition of a Set, Disjoint Sets, Singleton (Mathematics), Partitioning Problem.

---

---

References

• https://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf

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.

---