Disjoint-set data structure: Difference between revisions

Revision as of 00:46, 2 June 2022

Revision as of 02:05, 5 June 2022

Line 1:

{{Short description|Data structure for storing non-overlapping sets}}

{{Infobox data structure

|name=Disjoint-set/Union-find Forest

Line 16 ⟶ 17:

[[File:Dsu disjoint sets final.svg|thumb|360px|After some operations of <code>Union</code>, some sets are grouped together.]]

In [[computer science]], a '''disjoint-set data structure''', also called a '''union–find data structure''' or '''merge–find set''', is a [[data structure]] that stores a collection of [[Disjoint sets|disjoint]] (non-overlapping) [[Set (mathematics)|sets]]. Equivalently, it stores a [[partition of a set]] into disjoint subsets[[subset]]s. It provides operations for adding new sets, merging sets (replacing them by their [[Union (set theory)|union]]), and finding a representative member of a set. The last operation makes it possible to find out efficiently if any two elements are in the same or different sets.

While there are several ways of implementing disjoint-set data structures, in practice they are often identified with a particular implementation called a '''disjoint-set forest'''. This is a specialized type of [[Forest (graph theory)|forest]] which performs unions and finds in near -constant [[Amortized analysis|amortized time]]. To perform a sequence of {{mvar|m}} addition, union, or find operations on a disjoint-set forest with {{mvar|n}} nodes requires total time {{math|[[Big O notation|''O'']](''m''α(''n''))}}, where {{math|α(''n'')}} is the extremely slow-growing [[inverse Ackermann function]]. Disjoint-set forests do not guarantee this performance on a per-operation basis. Individual union and find operations can take longer than a constant times {{math|α(''n'')}} time, but each operation causes the disjoint-set forest to adjust itself so that successive operations are faster. Disjoint-set forests are both [[asymptotically optimal]] and practically efficient.

Disjoint-set data structures play a key role in [[Kruskal's algorithm]] for finding the [[minimum spanning tree]] of a graph. The importance of minimum spanning trees means that disjoint-set data structures underlie a wide variety of algorithms. In addition, disjoint-set data structures also have applications to symbolic computation, as well in compilers, especially for [[register allocation]] problems.