Disjoint Set Data Structure in Go

The disjoint set, also known as the union-find data structure, is used to keep track of a partition of a set into disjoint (non-overlapping) subsets. This data structure supports two primary operations efficiently:

• Find: Determine which subset a particular element is in. This operation can be used for determining if two elements are in the same subset.
• Union: Join two subsets into a single subset.

Program Structure

The Go program implementing the disjoint set data structure is structured into the following components:

1. DisjointSet Struct: This struct holds two slices: parent and rank. The parent slice is used to store the parent or representative of each element. The rank slice helps to keep the tree flat by attaching smaller trees under the root of the larger tree.
2. NewDisjointSet Function: This function initializes a new disjoint set with a specified number of elements. Each element is initially its own parent, representing a separate subset.
3. Find Method: This method recursively finds the representative (root) of the set containing a particular element. Path compression is used to make subsequent calls more efficient.
4. Union Method: This method merges two subsets into one by linking the roots of the sets. Union by rank is used to keep the tree shallow.

Go Code Implementation

// DisjointSet represents a disjoint set (union-find) data structure
type DisjointSet struct {
    parent []int
    rank   []int
}

// NewDisjointSet creates a new DisjointSet with n elements
func NewDisjointSet(n int) *DisjointSet {
    ds := &DisjointSet{
        parent: make([]int, n),
        rank:   make([]int, n),
    }
    for i := 0; i < n; i++ { ds.parent[i] = i // Each element is its own parent initially ds.rank[i] = 0 // The rank of each element is initially 0 } return ds } // Find finds the representative (root) of the set containing x // It also performs path compression to make future operations faster func (ds *DisjointSet) Find(x int) int { if ds.parent[x] != x { ds.parent[x] = ds.Find(ds.parent[x]) // Path compression } return ds.parent[x] } // Union unites the set containing x and the set containing y // It uses union by rank to keep the tree shallow func (ds *DisjointSet) Union(x, y int) { rootX := ds.Find(x) rootY := ds.Find(y) if rootX != rootY { if ds.rank[rootX] > ds.rank[rootY] {
            ds.parent[rootY] = rootX
        } else if ds.rank[rootX] < ds.rank[rootY] {
            ds.parent[rootX] = rootY
        } else {
            ds.parent[rootY] = rootX
            ds.rank[rootX]++
        }
    }
}

Explanation of the Code

Here’s a breakdown of the code:

• DisjointSet Struct: The parent slice stores the parent of each element, while the rank slice helps to keep the tree flat by tracking the depth of the trees.
• NewDisjointSet Function: This initializes a disjoint set for n elements. Each element is initialized as its own parent, and the rank is set to 0.
• Find Method: This method finds the root of the set containing x. If x is not its own parent, the method recursively finds the root and applies path compression by setting the parent of x directly to the root.
• Union Method: This method merges the sets containing x and y. It attaches the tree with a smaller rank under the root of the tree with a larger rank. If the ranks are equal, one tree is arbitrarily chosen as the new root, and its rank is incremented.

Usage Example

Here’s an example of how you might use this disjoint set implementation in a Go program:

func main() {
    ds := NewDisjointSet(5) // Create a disjoint set with 5 elements

    ds.Union(0, 1)
    ds.Union(1, 2)
    ds.Union(3, 4)

    fmt.Println(ds.Find(0)) // Output: 0 (root of the set containing 0)
    fmt.Println(ds.Find(2)) // Output: 0 (root of the set containing 2)
    fmt.Println(ds.Find(3)) // Output: 3 (root of the set containing 3)
}
    

Conclusion

This Go program demonstrates a basic yet efficient implementation of the disjoint set data structure using path compression and union by rank. The disjoint set is a powerful tool in many algorithms, including those for finding connected components in a graph, Kruskal’s algorithm for minimum spanning trees, and more.