Introduction to disjoint set data structure or union-find algorithm

The disjoint set information structure, also known as the union search algorithm, is probably a fundamental concept in computer science that provides an effective method for solving problems related to allocation and networking . It is particularly valuable for solving problems involving sets of components and determining their connections. In this article, we will look at language constructs, algorithms, and two unique ways to implement disjoint set information structures in C. We will also provide fully executable code examples illustrating these methods.

grammar

Before we delve into the algorithm, let’s familiarize ourselves with the syntax used in the following code examples -

// Create a disjoint set
DisjointSet ds(n);

// Perform union operation
ds.unionSets(a, b);

// Find the representative of a set
ds.findSet(x);

algorithm

Utilizing disjoint data structures can be very useful when dealing with multiple disjoint collections. Each individual grouping is assigned a specific representative to characterize it. The starting point involves each component forming its own isolated set, which corresponds to its respective representative (which also happens to be itself). The two main operations performed on disjoint sets are union and search.

Joint operation

• Find the representatives of the two sets to be merged.

• If the representatives are different, make one representative point to the other, effectively merging the sets.

• If the representatives are the same, the sets have been merged and no further action is required.

Find operation

• Given an element, find the representative of the set it belongs to.

• Follow the parent pointer until it reaches the representative node.

• Return the delegate as the result.

Method 1: Rank-based merging and path compression

An effective way to implement disjoint set data structures is to use rank-wise union and path compression techniques.

In this method, each collection has an associated rank, which is initially set to 0.

When performing a union operation between two sets, the higher-ranked set is given priority and the lower-ranked set is merged. If two sets have similar ranks, one must arbitrarily choose which set contains whom. In either case, once merged into a new set, its rank increases by 1. Additionally, to speed up lookup operations and reduce time complexity, path compression helps flatten the tree structure during these operations.

Example

Example

#include <iostream>
#include <vector>

class DisjointSet {
   std::vector<int> parent;
   std::vector<int> rank;
    
public:
   DisjointSet(int n) {
      parent.resize(n);
      rank.resize(n, 0);
      for (int i = 0; i < n; ++i)
         parent[i] = i;
   }
    
   int findSet(int x) {
      if (parent[x] != x)
         parent[x] = findSet(parent[x]);
      return parent[x];
   }
    
   void unionSets(int x, int y) {
      int xRoot = findSet(x);
      int yRoot = findSet(y);
        
      if (xRoot == yRoot)
         return;
        
      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() {
   // Example usage of DisjointSet
   int n = 5;  // Number of elements

   DisjointSet ds(n);

   ds.unionSets(0, 1);
   ds.unionSets(2, 3);
   ds.unionSets(3, 4);

   std::cout << ds.findSet(0) << std::endl;  
   std::cout << ds.findSet(2) << std::endl;  

   return 0;
}

Output

0
2

Method 2: Size-based merging with size and path compression

Another way to deal with disjoint set data structures is to use merge-by-size and path compression techniques.

• In this method, each collection has an associated size, initially set to 1.

• In a union operation, smaller sets are merged into larger sets.

• The size of the result set will be updated accordingly.

• Apply path compression during the seek operation to flatten the tree structure, similar to the previous method.

Example

Example

#include <iostream>
#include <vector>

class DisjointSet {
   std::vector<int> parent;
   std::vector<int> size;
    
public:
   DisjointSet(int n) {
      parent.resize(n);
      size.resize(n, 1);
      for (int i = 0; i < n; ++i)
         parent[i] = i;
   }
    
   int findSet(int x) {
      if (parent[x] != x)
         parent[x] = findSet(parent[x]);
      return parent[x];
   }
    
   void unionSets(int x, int y) {
      int xRoot = findSet(x);
      int yRoot = findSet(y);
        
      if (xRoot == yRoot)
         return;
        
      if (size[xRoot] < size[yRoot]) {
         parent[xRoot] = yRoot;
         size[yRoot] += size[xRoot];
      }
      else {
         parent[yRoot] = xRoot;
         size[xRoot] += size[yRoot];
      }
   }
};

int main() {
   // Example usage of DisjointSet
   int n = 5;  // Number of elements

   DisjointSet ds(n);

   ds.unionSets(0, 1);
   ds.unionSets(2, 3);
   ds.unionSets(3, 4);

   std::cout << ds.findSet(0) << std::endl;  
   std::cout << ds.findSet(2) << std::endl;  
   return 0;
}

Output

0
2

in conclusion

The disjoint set data structure or union search algorithm is a powerful tool for solving problems involving sets and connectivity. This article extensively studies C's disjoint set data structure syntax and its algorithms. To extend our understanding, we provide readers with two unique approaches - ranking-based union combined with path compression, and size-based union via size plus path compression. By understanding and implementing these methods, you can effectively solve a variety of problems that require tracking disjoint sets.

The above is the detailed content of Introduction to disjoint set data structure or union-find algorithm. For more information, please follow other related articles on the PHP Chinese website!