Editing Disjoint-set data structure (section)

== Applications ==

[[File:UnionFindKruskalDemo.gif|250px|thumb|A demo for Union-Find when using Kruskal's algorithm to find minimum spanning tree.]]

Disjoint-set data structures model the [[Partition of a set|partitioning of a set]], for example to keep track of the [[Connected component (graph theory)|connected components]] of an [[undirected graph]]. This model can then be used to determine whether two vertices belong to the same component, or whether adding an edge between them would result in a cycle.  The Union–Find algorithm is used in high-performance implementations of [[Unification (computer science)|unification]].<ref name="Knight1989">{{cite journal|last1=Knight|first1=Kevin|year=1989|title=Unification: A multidisciplinary survey|journal=ACM Computing Surveys|pages=93&ndash;124|doi=10.1145/62029.62030|volume=21|s2cid=14619034|url=http://www.isi.edu/natural-language/people/unification-knight.pdf }}</ref>

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]] uses a Union-Find in the algorithm.