Disjoint-set data structure: Difference between revisions

Revision as of 20:26, 4 October 2004

Revision as of 05:43, 18 October 2004

Line 2:

* '''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.

Because it supports these two operations, a disjoint-set data structure is sometimes called a '''merge-find set'''. 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).

WhileIn weorder couldto representdefine thethese groupsoperations themselvesmore asprecisely objectswe andneed havesome theway operationsof operate on these sets,representing the moregroups. One common approach is to chooseselect a anfixed element fromof each group, ascalled aits ''representative'';, to represent the group as a whole. thenThen, '''Find'''(x) returns the representative of the group that the''x'' givenbelongs element is into, and '''Union''' takes thetwo group representatives ofas twoits given groupsarguments.

== Disjoint-set linked lists ==