Jump to content

Disjoint-set data structure

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Dcoetzee (talk | contribs) at 22:21, 3 October 2004 (Wrote intro). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.
(diff) ← Previous revision | Latest revision (diff) | Newer revision → (diff)

In computer science, a disjoint-set data structure is a data structure that assigns each element in a set to one of a number of disjoint (nonoverlapping) groups of elements. A union-find algorithm is a way of performing two critical operations on such a data structure:

  • Find: Determine which group a particular element is in.
  • Union: Combine two groups into a single group.


References

  • Introduction to Algorithms, 2nd ed. Cormen, Leiserson, Rivest, Stein. ISBN 0262032937.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Disjoint-set_data_structure&oldid=6319044"