|
|
Disjoint Set
Introduction
A Disjoint Set data structure keeps track of a set of elements partitioned into a number of disjoint subsets.
Disjoint Set supports the following operations:
- Determine a subset to which a given element belongs. This can be used for determining if two elements are in the same subset.
- Join two subsets into a one new subset.
- Create a new subset from the element.
The computational complexity of these operations are near constant. This allows to solve certain problems on Graphs very efficiently.
See for example Kruskal's algorithm.
Implementation
C# implementation - Open on Github
This implementation includes the path compression and union by rank optimizations.
Problems
Links
|