📚 dsu - Awesome Go Library for Data Structures and Algorithms
Disjoint Set data structure implementation in Go.
🏷️ Data Structures and Algorithms
📂 Frameworks for performing ELT / ETL
⭐ 14 stars
Detailed Description of dsu
dsu
Implementation of the Disjoint-Set data structure. The Disjoint-Set, Also called a Union-Find or Merge-Find set, is a data structure that stores a collection of disjoint (non-overlapping) sets. Equivalently, it stores a partition of a set into disjoint subsets. It provides operations for adding new sets, merging sets (replacing them by their union), and finding a representative member of a set. The last operation allows to find out efficiently if any two elements are in the same or different sets.
Installation
go get github.com/ihebu/dsu
Documentation
You can check the code documentation here
Usage Example
// Create a new disjoint-set
d := dsu.New()
// Add the elements 1, 2, 3 to the set
d.Add(1)
d.Add(2)
d.Add(3)
// The set is now {1}, {2}, {3}
// Unite the sets {1}, {2}
d.Union(1, 2)
// The set is now {1, 2}, {3}
// Find the representative element of each set
d.Find(1) // returns 2
d.Find(2) // returns 2
d.Find(3) // returns 3
// Check the existence of an element in the set
d.Contains(2) // returns true
d.Contains(54) // returns false
// Note : you can add elements of different type in the set
// Example
d.Add("hello")
d.Add(34.5)
d.Union("hello", 34.5)