Disjoint-set data structure: Difference between revisions

Revision as of 20:09, 10 March 2024

Revision as of 21:17, 12 May 2024

Line 21:

== History ==

Disjoint-set forests were first described by [[Bernard A. Galler]] and [[Michael J. Fischer]] in 1964.<ref name="Galler1964">{{cite journal|first1=Bernard A.|last1=Galler|author1-link=Bernard A. Galler|first2=Michael J.|last2=Fischer|author2-link=Michael J. Fischer|title=An improved equivalence algorithm|journal=[[Communications of the ACM]]|volume=7|issue=5|date=May 1964|pages=301–303|doi=10.1145/364099.364331|s2cid=9034016 |doi-access=free}}. The paper originating disjoint-set forests.</ref> In 1973, their time complexity was bounded to <math>O(\log^{*}(n))</math>, the [[iterated logarithm]] of <math>n</math>, by [[John Hopcroft|Hopcroft]] and [[Jeffrey Ullman|Ullman]].<ref name="Hopcroft1973">{{cite journal|last1=Hopcroft|first1=J. E.|author1-link=John Hopcroft|last2=Ullman|first2=J. D.|author2-link=Jeffrey Ullman|year=1973|title=Set Merging Algorithms|journal=SIAM Journal on Computing|volume=2|issue=4|pages=294&ndash;303|doi=10.1137/0202024}}</ref> In 1975, [[Robert Tarjan]] was the first to prove the <math>O(m\alpha(n))</math> ([[Ackermann function#Inverse|inverse Ackermann function]]) upper bound on the algorithm's time complexity,.<ref name="Tarjan1984">{{cite journal|first1=Robert E.|last1=Tarjan|author1-link=Robert E. Tarjan|first2=Jan|last2=van Leeuwen|author2-link=Jan van Leeuwen|title=Worst-case analysis of set union algorithms|journal=Journal of the ACM|volume=31|issue=2|pages=245–281|year=1984|doi= 10.1145/62.2160|s2cid=5363073 |doi-access=free}}</ref>. He also proved it to be tight. In 1979, he showed that this was the lower bound for a certain class of algorithms, that include the Galler-Fischer structure.<ref name="Tarjan1979">{{cite journal|first=Robert Endre|last=Tarjan|author-link=Robert E. Tarjan|year=1979|title=A class of algorithms which require non-linear time to maintain disjoint sets|journal=Journal of Computer and System Sciences|volume=18|issue=2|pages=110&ndash;127|doi=10.1016/0022-0000(79)90042-4|doi-access=free }}</ref> In 1989, [[Michael Fredman|Fredman]] and [[Michael Saks (mathematician)|Saks]] showed that <math>\Omega(\alpha(n))</math> (amortized) words of <math>O(\log n)</math> bits must be accessed by ''any'' disjoint-set data structure per operation,<ref name="Fredman1989">{{cite book|first1=M.|last1=Fredman|author-link=Michael Fredman|first2=M.|last2=Saks|title=Proceedings of the twenty-first annual ACM symposium on Theory of computing - STOC '89 |chapter=The cell probe complexity of dynamic data structures |pages=345&ndash;354|date=May 1989|doi=10.1145/73007.73040|isbn=0897913078|s2cid=13470414|quote=Theorem 5: Any CPROBE(log ''n'') implementation of the set union problem requires Ω(''m'' α(''m'', ''n'')) time to execute ''m'' Find's and ''n''&minus;1 Union's, beginning with ''n'' singleton sets. |doi-access=free}}</ref> thereby proving the optimality of the data structure in this model.

In 1991, Galil and Italiano published a survey of data structures for disjoint-sets.<ref name="Galil1991">{{cite journal|first1=Z.|last1=Galil|first2=G.|last2=Italiano|title=Data structures and algorithms for disjoint set union problems|journal=ACM Computing Surveys|volume=23|issue=3|pages=319&ndash;344|year=1991|doi=10.1145/116873.116878|s2cid=207160759 }}</ref>

Line 262:

This data structure is used by the [[Boost Graph Library]] to implement its [http://www.boost.org/libs/graph/doc/incremental_components.html Incremental Connected Components] functionality. It is also a key component in implementing [[Kruskal's algorithm]] to find the [[minimum spanning tree]] of a graph.

The [[Hoshen–Kopelman_algorithm|Hoshen–Kopelman algorithm|Hoshen-Kopelman algorithm]] uses a Union-Find in the algorithm.

== See also ==