Level merging and path compression in union-find algorithm

Algorithms called union-find sets (or disjoint sets) are responsible for maintaining distinct sets and providing operations to verify membership in the sets and combine sets together. It handles union and lookup operations expertly, which is crucial for maintaining current connection information between elements.

grammar

To ensure clarity, let's first understand the syntax of the methods we are about to use in the following code examples.

// Method to perform Union operation
void Union(int x, int y);

// Method to find the representative element of a set
int Find(int x);

algorithm

The union search algorithm consists of two basic operations - union and search. The union operation combines two sets, and the search operation determines the representative element of the set. By iteratively applying the union lookup operation, we can build efficient union lookup data structures.

United by level

The join-by-level technique is used to optimize join operations by ensuring that smaller trees are always attached to the root of larger trees. This approach prevents the tree from becoming too unbalanced, resulting in inefficient lookup operations.

The algorithm for union by level is as follows -

• Find the representative (root element) of the set containing elements x and y.

• If the representatives are the same, return.

• If the level of x's representative is greater than the level of y's representative, make y's representative point to x's representative and update the level of x's representative.

• Otherwise, make x's representative point to y's representative, and update y's representative's ranking if necessary.

Path compression

Path compression is another optimization technique that reduces the height of the tree in the query data structure. Its purpose is to flatten the path during a seek operation, thus providing a shorter path for subsequent operations.

• The algorithm for path compression is as follows -

• Find the representative (root element) of the set containing element x.

• When traversing the path from x to its representative, make each visited element point directly to the representative.

method

Now that we understand the basic concepts of rank-wise union and path compression, let's discuss two different ways to implement the union search algorithm in C.

Method 1: Array-based implementation

In this approach, we represent each collection as an array. The value at each index represents the element's parent element. Initially, each element is its own parent, indicating that it is a representative of its collection.

algorithm

• Let's start the initialization process of the parent array. Each element will be assigned its own parent element.

• Use path compression to implement search operations.

• Use Union by Rank to implement Union operation.

Example

#include <iostream>
#define MAX_SIZE 100

// Initialize parent array
int parent[MAX_SIZE];
int rank[MAX_SIZE];

void makeSet(int n) {
   for (int i = 0; i < n; i++) {
      parent[i] = i;
      rank[i] = 0;
   }
}

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

void Union(int x, int y) {
   int xRoot = find(x);
   int yRoot = find(y);
    
   if (xRoot == yRoot) {
      return;
   }
    
   // Union by rank
   if (rank[xRoot] < rank[yRoot]) {
      parent[xRoot] = yRoot;
   } else if (rank[xRoot] > rank[yRoot]) {
      parent[yRoot] = xRoot;
   } else {
      parent[yRoot] = xRoot;
      rank[xRoot]++;
   }
}

int main() {
   // Usage example
   makeSet(10); // Assuming 10 elements in the set
   Union(1, 2);
   Union(3, 4);
    
   // Print parent array
   for (int i = 0; i < 10; i++) {
      std::cout << "Element " << i << " Parent: " << parent[i] << std::endl;
   }
    
   return 0;
}

Output

Element 0 Parent: 0
Element 1 Parent: 1
Element 2 Parent: 1
Element 3 Parent: 3
Element 4 Parent: 3
Element 5 Parent: 5
Element 6 Parent: 6
Element 7 Parent: 7
Element 8 Parent: 8
Element 9 Parent: 9

Method 2: Tree-based implementation

To describe the collections in our study, we used a tree-based approach. Each item in the group is associated with its respective parent node, and we specify the root node to represent that specific collection.

algorithm

• Initialize the parent array, where each element is its own parent element.

• Use path compression and recursive tree traversal to implement search operations.

• Use Union by Rank to implement Union operation.

• Complete executable code

Example

#include <iostream>

#define MAX_SIZE 100

// Initialize parent array
int parent[MAX_SIZE];
int rank[MAX_SIZE];

void makeSet(int n) {
   for (int i = 0; i < n; i++) {
      parent[i] = i;
      rank[i] = 0;
   }
}

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

void Union(int x, int y) {
   int xRoot = find(x);
   int yRoot = find(y);
   
   if (xRoot == yRoot) {
      return;
   }
    
   // Union by rank
   if (rank[xRoot] < rank[yRoot]) {
      parent[xRoot] = yRoot;
   } else if (rank[xRoot] > rank[yRoot]) {
      parent[yRoot] = xRoot;
   } else {
      parent[yRoot] = xRoot;
      rank[xRoot]++;
   }
}

int main() {
   // Usage example
   makeSet(10); // Assuming 10 elements in the set
   Union(1, 2);
   Union(3, 4);
    
   // Print parent array
   for (int i = 0; i < 10; i++) {
      std::cout << "Element " << i << " Parent: " << parent[i] << std::endl;
   }
    
   return 0;
}

Output

Element 0 Parent: 0
Element 1 Parent: 1
Element 2 Parent: 1
Element 3 Parent: 3
Element 4 Parent: 3
Element 5 Parent: 5
Element 6 Parent: 6
Element 7 Parent: 7
Element 8 Parent: 8
Element 9 Parent: 9

in conclusion

In short, hierarchical union and path compression are key technologies in the union search algorithm. They optimize union and lookup operations respectively, resulting in improved performance and efficient connection information management. By implementing these techniques in C, we can efficiently solve problems related to sets, connectivity, and graphs.

To summarize, we introduced the syntax, step-by-step algorithm, and provided two real C executable code examples. By understanding and applying rank-wise union and path compression, you can enhance your algorithmic skills and solve complex problems more efficiently.

The above is the detailed content of Level merging and path compression in union-find algorithm. For more information, please follow other related articles on the PHP Chinese website!