Introduction à la structure de données d'ensembles disjoints ou à l'algorithme de recherche d'union

La structure d'information des ensembles disjoints, également connue sous le nom d'algorithme de recherche d'union, est probablement un concept fondamental en informatique, qui fournit une méthode efficace pour résoudre les problèmes liés à l'allocation et à la mise en réseau. Il est particulièrement utile pour résoudre des problèmes impliquant des ensembles de composants et déterminer leurs connexions. Dans cet article, nous examinerons les constructions de langage, les algorithmes et deux manières uniques d'implémenter des structures d'informations d'ensembles disjoints en C++. Nous fournirons également des exemples de code entièrement exécutables illustrant ces méthodes.

Grammaire

Avant d'entrer dans l'algorithme, familiarisons-nous avec la syntaxe utilisée dans les exemples de code suivants -

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

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

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

Algorithme

Exploiter des structures de données disjointes peut être très utile lorsqu'il s'agit de plusieurs collections disjointes. Chaque groupement individuel se voit attribuer un représentant spécifique pour le caractériser. Le point de départ implique que chaque composant forme son propre ensemble isolé, qui correspond à son représentant respectif (qui se trouve aussi être lui-même). Les deux principales opérations effectuées sur des ensembles disjoints sont l'union et la recherche.

Opération conjointe

• Trouvez les représentants des deux ensembles que vous souhaitez fusionner.

• Si les délégués sont différents, faites valoir un point sur l'autre, fusionnant ainsi efficacement les ensembles.

• Si les représentants sont les mêmes, les ensembles ont été fusionnés et aucune autre action n'est requise.

Trouver une opération

• Étant donné un élément, trouvez le représentant de l'ensemble auquel il appartient.

• Suivez le pointeur parent jusqu'à ce qu'il atteigne le nœud représentatif.

• Renvoyez le délégué comme résultat.

Méthode 1 : Fusion basée sur le classement et compression de chemin

Un moyen efficace d'implémenter des structures de données d'ensembles disjoints consiste à utiliser des techniques d'union par rang et de compression de chemin.

Dans cette méthode, chaque collection a un rang associé, initialement fixé à 0.

Lors de l'exécution d'une opération d'union entre deux ensembles, l'ensemble le mieux classé est prioritaire et l'ensemble le moins bien classé est fusionné. Si deux ensembles ont des rangs similaires, il faut choisir arbitrairement quel ensemble contient qui. Dans les deux cas, une fois fusionné dans un nouvel ensemble, son rang augmente de 1. De plus, pour accélérer les opérations de recherche et réduire la complexité temporelle, la compression des chemins permet d'aplatir la structure arborescente au cours de ces opérations.

Exemple

Exemple

#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;
}

Sortie

0
2

Méthode 2 : Fusion basée sur la taille avec compression de taille et de chemin

Une autre façon de gérer les structures de données d'ensembles disjoints consiste à utiliser des techniques de fusion par taille et de compression de chemin.

• Dans cette méthode, chaque collection a une taille associée, initialement fixée à 1.

• Dans une opération syndicale, les ensembles plus petits sont fusionnés en ensembles plus grands.

• La taille de l'ensemble de résultats sera mise à jour en conséquence.

• Appliquez une compression de chemin pendant l'opération de recherche pour aplatir la structure arborescente, similaire à la méthode précédente.

Exemple

Exemple

#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;
}

Sortie

0
2

Conclusion

La structure de données d'ensembles disjoints ou algorithme de recherche d'union est un outil puissant pour résoudre les problèmes impliquant les ensembles et la connectivité. Cet article étudie en profondeur la syntaxe de la structure de données des ensembles disjoints du C++ et ses algorithmes. Pour élargir notre compréhension, nous proposons aux lecteurs deux approches uniques : l'union basée sur le classement combinée à la compression du chemin, et l'union basée sur la taille via la compression de la taille et du chemin. En comprenant et en mettant en œuvre ces méthodes, vous pouvez résoudre efficacement divers problèmes nécessitant le suivi d’ensembles disjoints.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!