Ebenenzusammenführung und Pfadkomprimierung im Union-Find-Algorithmus

Ein Algorithmus, der Union-Find-Set (oder disjunkte Menge) genannt wird, ist für die Verwaltung verschiedener Mengen und die Bereitstellung von Operationen zur Überprüfung der Zugehörigkeit zu den Mengen und zum Kombinieren der Mengen verantwortlich. Es verarbeitet Vereinigungs- und Suchvorgänge fachmännisch, was für die Aufrechterhaltung aktueller Verbindungsinformationen zwischen Elementen von entscheidender Bedeutung ist.

Grammatik

Zur Verdeutlichung wollen wir zunächst die Syntax der Methoden verstehen, die wir in den folgenden Codebeispielen verwenden werden.

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

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

Algorithmus

Der Union-Suchalgorithmus besteht aus zwei Grundoperationen – Union und Suche. Die Vereinigungsoperation kombiniert zwei Mengen und die Suchoperation bestimmt das repräsentative Element der Menge. Durch die iterative Anwendung der Union-Lookup-Operation können wir effiziente Union-Lookup-Datenstrukturen erstellen.

Vereint nach Level

Die Join-by-Level-Technik wird verwendet, um Join-Vorgänge zu optimieren, indem sichergestellt wird, dass kleinere Bäume immer an der Wurzel größerer Bäume befestigt werden. Dieser Ansatz verhindert, dass der Baum zu unausgeglichen wird, was zu ineffizienten Suchvorgängen führt.

Der Algorithmus zur Vereinigung nach Ebenen ist wie folgt -

• Finden Sie den Vertreter (Wurzelelement) der Menge, die die Elemente x und y enthält.

• Wenn die Vertreter gleich sind, kehren Sie zurück.

• Wenn die Ebene des Repräsentanten von x größer ist als die Ebene des Repräsentanten von y, veranlassen Sie den Repräsentanten von y, auf den Repräsentanten von

• Andernfalls weisen Sie den Vertreter von x auf den Vertreter von y hin und aktualisieren Sie bei Bedarf die Rangfolge des Vertreters von y.

Pfadkomprimierung

Pfadkomprimierung ist eine weitere Optimierungstechnik, die die Höhe des Baums in der Abfragedatenstruktur reduziert. Sein Zweck besteht darin, den Pfad während eines Suchvorgangs abzuflachen und so einen kürzeren Pfad für nachfolgende Vorgänge bereitzustellen.

• Der Algorithmus der Pfadkomprimierung ist wie folgt:

• Finden Sie den Vertreter (Wurzelelement) der Menge, die das Element x enthält.

• Wenn Sie den Pfad von x zu seinem Vertreter durchlaufen, achten Sie darauf, dass jedes besuchte Element direkt auf den Vertreter zeigt.

Methode

Da wir nun die grundlegenden Konzepte der rangweisen Vereinigung und der Pfadkomprimierung verstanden haben, diskutieren wir zwei verschiedene Möglichkeiten zur Implementierung des Union-Suchalgorithmus in C++.

Methode 1: Array-basierte Implementierung

Bei dieser Methode stellen wir jede Sammlung als Array dar. Der Wert an jedem Index stellt das übergeordnete Element des Elements dar. Zunächst ist jedes Element sein eigenes übergeordnetes Element, was darauf hinweist, dass es ein Repräsentant seiner Sammlung ist.

Algorithmus

• Lassen Sie uns den Initialisierungsprozess des übergeordneten Arrays starten. Jedem Element wird ein eigenes übergeordnetes Element zugewiesen.

• Verwenden Sie die Pfadkomprimierung, um Suchvorgänge zu implementieren.

• Verwenden Sie Union by Rank, um die Union-Operation zu implementieren.

Beispiel

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

Ausgabe

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

Methode 2: Baumbasierte Implementierung

Um die Sammlungen in unserer Studie zu beschreiben, haben wir einen baumbasierten Ansatz verwendet. Jedes Element in der Gruppe ist seinem jeweiligen übergeordneten Knoten zugeordnet, und wir geben den Stammknoten an, der diese spezifische Sammlung darstellt.

Algorithmus

• Initialisieren Sie das übergeordnete Array, wobei jedes Element sein eigenes übergeordnetes Element ist.

• Verwenden Sie Pfadkomprimierung und rekursive Baumdurchquerung, um Suchvorgänge zu implementieren.

• Verwenden Sie Union by Rank, um die Union-Operation zu implementieren.

• Vollständiger ausführbarer Code

Beispiel

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

Ausgabe

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

Fazit

Kurz gesagt, hierarchische Vereinigung und Pfadkomprimierung sind Schlüsseltechnologien im Vereinigungssuchalgorithmus. Sie optimieren Vereinigungs- bzw. Suchvorgänge, was zu einer verbesserten Leistung und einem effizienten Verbindungsinformationsmanagement führt. Durch die Implementierung dieser Techniken in C++ können wir Probleme im Zusammenhang mit Mengen, Konnektivität und Diagrammen effizient lösen.

Zusammenfassend haben wir die Syntax und den Schritt-für-Schritt-Algorithmus vorgestellt und zwei echte Beispiele für ausführbaren C++-Code bereitgestellt. Durch das Verständnis und die Anwendung der rangweisen Vereinigungs- und Pfadkomprimierung können Sie Ihre algorithmischen Fähigkeiten verbessern und komplexe Probleme effizienter lösen.

Das obige ist der detaillierte Inhalt vonEbenenzusammenführung und Pfadkomprimierung im Union-Find-Algorithmus. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!