The Union–Find data structure for maintaining disjoint sets is one of the best known and widespread data structures, in particular the version with constant-time Union and efficient Find. (Yoffe et al. 2010)
Union-Find Algorithm is an algorithm which uses a disjoint-set data structure to solve problems that are related to merging any two items that observes equality between them. This algorithm performs two useful operations on such data structure:
- UNION : Combine or merge two sets into a single set.
- FIND : Determine which set a particular element is in. Also useful for determining if two elements are in the same set.
This is a common way to find connectivity between nodes, or to find connected components. This algorithm is also used to solve partitioning problems or deciding when to make partitions of a given multiset.
Union-Find Algorithm is somewhat necessary for the implementation of Kruskal's Algorithm because it uses the operations union and find. The data structure therefore supports the operations, Makeset, Union and Find. The Union-Find can also be thought of as a way to maipulate disjoint sets, which is just a more general view of equivalence classes.
other links cited:
