Disjoint-set data structure: Difference between revisions

Revision as of 19:56, 4 October 2004

Revision as of 20:00, 4 October 2004

Line 4:

The other important operation, '''MakeSet''', which makes a group 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 setsgroups themselves as objects and have the operations operate on these sets, the more common approach is to choose an element from each setgroup as a ''representative''; then, '''Find''' returns the representative of the setgroup that the given element is in, and '''Union''' takes the representatives of two given setsgroups.

== Disjoint-set linked lists ==