A non-invasive disjoint-set-like data structure implementation in Rust
MIT License
A non-invasive implementation of a disjoint-set tree data structure, written in Rust.
Disjoint sets data structure, or DSU, or union-find data structure, or merge- find set, is a data structure that stores a collection of disjoint sets. It provides operations for adding new sets, merging sets (equivalent to replacing the sets with the union of them) and finding the representative member of a set. DSU is very useful in implementing algorithms like minimum spanning tree and more.
DSU can be implemented with its extreme efficiency by using disjoint-set trees. Disjoint-set trees are actually a forest in which each node represents a set and each tree represents the union of sets that are merged together. The three DSU operations can be implemented as follows:
A
and B
, respectively, we just change the parent node of A
to B
and it's done. In real implementations, some corner cases need to be considered, such as merging a set into itself.Rather than implementing a disjoint-set data structure, this crate provides the implementation of the underlying disjoint-set tree data structure.
For the usage of this library, please refer to the documentation.
This library is open-sourced under MIT License.