What Is Disjoint-Set Data Structure in C?

//

Heather Bennett

The Disjoint-Set data structure, also known as the Union-Find data structure, is a key concept in computer science and plays a crucial role in various algorithms. It is used to efficiently keep track of a partition of a set into disjoint subsets.

What is a Disjoint-Set?
A disjoint-set is a collection of non-overlapping sets. Each set consists of elements that are distinct from the elements in other sets. In other words, no two sets have any common elements.

Key Operations:
The Disjoint-Set data structure supports two main operations:

• MakeSet(x):
• This operation creates a new set with an initial element x. It initializes the representative pointer of x to itself, indicating that it is the representative (or root) of its own set.

• Union(x, y):
• This operation merges two existing sets containing elements x and y respectively. It finds the representatives (roots) of these sets and makes one of them the parent of the other, thus creating a new larger set.

Path Compression Optimization:
One common optimization technique used with the Disjoint-Set data structure is path compression. It aims to reduce the height (or depth) of the tree-like representation formed by the sets.

When finding the representative (root) for an element, path compression ensures that all elements along the path from that element to its root have their representative pointers updated directly to point to the root. This optimization helps achieve near-constant time complexity for subsequent find operations.

Implementation in C:

To implement Disjoint-Set in C, we can use arrays to store parent pointers and additional information like rank or size.

Here’s an example implementation:

“`c
#include

#define MAX_SIZE 1000

int parent[MAX_SIZE];
int rank[MAX_SIZE];

void makeSet(int x) {
parent[x] = x;
rank[x] = 0;
}

int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // Path compression optimization
}
return parent[x];
}

void unionSets(int x, int y) {
int rootX = find(x);
int rootY = find(y);

if (rootX == rootY)
return;

// Union by rank optimization
if (rank[rootX] < rank[rootY]) { parent[rootX] = rootY; } else if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else { // If ranks are equal, choose either representative as the new root
parent[rootY] = rootX;
rank[rootX]++;
}
}

int main() {
// Usage example
makeSet(1);
makeSet(2);
makeSet(3);

unionSets(1, 2);
unionSets(2, 3);

printf(“Representative of element 3: %d\n”, find(3)); // Output: 1

return 0;
}
“`

Conclusion:

The Disjoint-Set data structure is a powerful tool that enables efficient manipulation of disjoint sets. Its applications include graph algorithms like Kruskal’s algorithm for finding minimum spanning trees and detecting cycles in a graph.

By understanding the concepts of representatives, unions, and path compression optimizations, you can leverage this data structure to solve various problems effectively.

So go ahead and explore the world of Disjoint-Sets to unlock new possibilities in your programming journey!

Privacy Policy