Fusion de niveaux et compression de chemin dans l'algorithme de recherche d'union

Un algorithme appelé ensemble de recherche d'union (ou ensemble disjoint) est chargé de maintenir différents ensembles et de fournir des opérations pour vérifier l'appartenance aux ensembles et combiner les ensembles entre eux. Il gère de manière experte les opérations d'union et de recherche, qui sont essentielles au maintien des informations de connexion actuelles entre les éléments.

Grammaire

Pour plus de clarté, comprenons d'abord la syntaxe des méthodes que nous allons utiliser dans les exemples de code suivants.

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

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

Algorithme

L'algorithme de recherche d'union se compose de deux opérations de base : l'union et la recherche. L'opération d'union combine deux ensembles et l'opération de recherche détermine l'élément représentatif de l'ensemble. En appliquant de manière itérative l’opération de recherche d’union, nous pouvons créer des structures de données de recherche d’union efficaces.

Unis par niveau

La technique de jointure par niveau est utilisée pour optimiser les opérations de jointure en garantissant que les arbres plus petits sont toujours attachés à la racine des arbres plus grands. Cette approche évite que l'arborescence ne devienne trop déséquilibrée, ce qui entraînerait des opérations de recherche inefficaces.

L'algorithme d'union par niveau est le suivant -

• Trouvez le représentant (élément racine) de l'ensemble contenant les éléments x et y.

• Si les représentants sont les mêmes, revenez.

• Si le niveau du représentant de x est supérieur au niveau du représentant de y, faites pointer le représentant de y vers le représentant de x et mettez à jour le niveau du représentant de x.

• Sinon, faites pointer le représentant de x vers le représentant de y et mettez à jour le classement du représentant de y si nécessaire.

Compression du chemin

La compression du chemin est une autre technique d'optimisation qui réduit la hauteur de l'arborescence dans la structure des données de la requête. Son objectif est d'aplatir le chemin lors d'une opération de recherche, fournissant ainsi un chemin plus court pour les opérations ultérieures.

• L'algorithme de compression de chemin est le suivant -

• Trouvez le représentant (élément racine) de l'ensemble contenant l'élément x.

• Lorsque vous parcourez le chemin de x à son représentant, faites en sorte que chaque élément visité pointe directement vers le représentant.

Méthode

Maintenant que nous comprenons les concepts de base de l'union par rang et de la compression de chemin, discutons de deux manières différentes d'implémenter l'algorithme de recherche d'union en C++.

Méthode 1 : implémentation basée sur un tableau

Dans cette méthode, nous représentons chaque collection sous forme de tableau. La valeur à chaque index représente l'élément parent de l'élément. Initialement, chaque élément est son propre parent, indiquant qu'il est représentatif de sa collection.

Algorithme

• Commençons le processus d'initialisation du tableau parent. Chaque élément se verra attribuer son propre élément parent.

• Utilisez la compression de chemin pour implémenter les opérations de recherche.

• Utilisez Union by Rank pour mettre en œuvre le fonctionnement de l'Union.

Exemple

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

Sortie

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

Méthode 2 : Implémentation basée sur un arbre

Pour décrire les collections de notre étude, nous avons utilisé une approche arborescente. Chaque élément du groupe est associé à son nœud parent respectif et nous spécifions le nœud racine pour représenter cette collection spécifique.

Algorithme

• Initialisez le tableau parent où chaque élément est son propre parent.

• Utilisez la compression de chemin et la traversée récursive d'arbres pour implémenter les opérations de recherche.

• Utilisez Union by Rank pour mettre en œuvre le fonctionnement de l'Union.

• Code exécutable complet

Exemple

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

Sortie

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

Conclusion

En bref, l'union hiérarchique et la compression de chemin sont des technologies clés dans l'algorithme de recherche d'union. Ils optimisent respectivement les opérations d'union et de recherche, ce qui entraîne des performances améliorées et une gestion efficace des informations de connexion. En implémentant ces techniques en C++, nous pouvons résoudre efficacement les problèmes liés aux ensembles, à la connectivité et aux graphiques.

Pour résumer, nous avons présenté la syntaxe, l'algorithme étape par étape et fourni deux vrais exemples de code exécutable C++. En comprenant et en appliquant l'union par rang et la compression de chemin, vous pouvez améliorer vos compétences algorithmiques et résoudre des problèmes complexes plus efficacement.

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!