Einführung in die Datenstruktur disjunkter Mengen oder den Union-Find-Algorithmus

Die disjunkte Mengeninformationsstruktur, auch Union-Search-Algorithmus genannt, ist wahrscheinlich ein grundlegendes Konzept in der Informatik, das eine effiziente Methode zur Lösung von Problemen im Zusammenhang mit Zuordnung und Vernetzung bietet. Es ist besonders wertvoll für die Lösung von Problemen mit Komponentensätzen und der Bestimmung ihrer Verbindungen. In diesem Artikel befassen wir uns mit Sprachkonstrukten, Algorithmen und zwei einzigartigen Möglichkeiten zur Implementierung disjunkter Mengeninformationsstrukturen in C++. Wir werden auch vollständig ausführbare Codebeispiele bereitstellen, die diese Methoden veranschaulichen.

Grammatik

Bevor wir uns mit dem Algorithmus befassen, machen wir uns mit der Syntax vertraut, die in den folgenden Codebeispielen verwendet wird -

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

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

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

Algorithmus

Die Nutzung disjunkter Datenstrukturen kann beim Umgang mit mehreren disjunkten Sammlungen sehr nützlich sein. Jeder einzelnen Gruppierung wird zur Charakterisierung ein spezifischer Vertreter zugeordnet. Der Ausgangspunkt besteht darin, dass jede Komponente eine eigene isolierte Menge bildet, die ihrem jeweiligen Repräsentanten (der zufällig auch sie selbst ist) entspricht. Die beiden Hauptoperationen, die an disjunkten Mengen durchgeführt werden, sind Vereinigung und Suche.

Gemeinsamer Betrieb

• Finden Sie die Vertreter der beiden Mengen, die Sie zusammenführen möchten.

• Wenn die Delegierten unterschiedlich sind, verknüpfen Sie einen Punkt mit dem anderen und führen so die Sätze effektiv zusammen.

• Wenn die Vertreter identisch sind, wurden die Sets zusammengeführt und es sind keine weiteren Maßnahmen erforderlich.

Betrieb finden

• Suchen Sie bei einem gegebenen Element den Vertreter der Menge, zu der es gehört.

• Folgen Sie dem übergeordneten Zeiger, bis er den repräsentativen Knoten erreicht.

• Den Delegaten als Ergebnis zurückgeben.

Methode 1: Rangbasierte Zusammenführung und Pfadkomprimierung

Eine effektive Möglichkeit, disjunkte Mengendatenstrukturen zu implementieren, ist die Verwendung von rangweisen Vereinigungs- und Pfadkomprimierungstechniken.

Bei dieser Methode ist jeder Sammlung ein Rang zugeordnet, der zunächst auf 0 gesetzt ist.

Beim Durchführen einer Vereinigungsoperation zwischen zwei Mengen erhält die höherrangige Menge Vorrang und die niedrigerrangige Menge wird zusammengeführt. Wenn zwei Mengen ähnliche Ränge haben, muss man willkürlich auswählen, welche Menge wen enthält. In beiden Fällen erhöht sich der Rang nach der Zusammenführung mit einem neuen Set um 1. Um Suchvorgänge zu beschleunigen und die Zeitkomplexität zu reduzieren, hilft die Pfadkomprimierung außerdem dabei, die Baumstruktur während dieser Vorgänge zu verflachen.

Beispiel

Beispiel

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

Ausgabe

0
2

Methode 2: Größenbasiertes Zusammenführen mit Größen- und Pfadkomprimierung

Eine andere Möglichkeit, mit disjunkten Mengendatenstrukturen umzugehen, ist die Verwendung von Merge-by-Size- und Pfadkomprimierungstechniken.

• Bei dieser Methode ist jeder Sammlung eine Größe zugeordnet, die zunächst auf 1 eingestellt ist.

• Bei einer Vereinigungsoperation werden kleinere Mengen zu größeren Mengen zusammengeführt.

• Die Größe der Ergebnismenge wird entsprechend aktualisiert.

• Wenden Sie während des Suchvorgangs eine Pfadkomprimierung an, um die Baumstruktur zu verflachen, ähnlich wie bei der vorherigen Methode.

Beispiel

Beispiel

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

Ausgabe

0
2

Fazit

Die disjunkte Mengendatenstruktur oder der Union-Suchalgorithmus ist ein leistungsstarkes Werkzeug zur Lösung von Problemen im Zusammenhang mit Mengen und Konnektivität. In diesem Artikel werden die Syntax der disjunkten Mengendatenstruktur von C++ und ihre Algorithmen ausführlich untersucht. Um unser Verständnis zu erweitern, stellen wir den Lesern zwei einzigartige Ansätze zur Verfügung: rangbasierte Vereinigung kombiniert mit Pfadkomprimierung und größenbasierte Vereinigung mittels Größe plus Pfadkomprimierung. Durch das Verständnis und die Implementierung dieser Methoden können Sie eine Vielzahl von Problemen effektiv lösen, die die Verfolgung disjunkter Mengen erfordern.

Das obige ist der detaillierte Inhalt vonEinführung in die Datenstruktur disjunkter Mengen oder den Union-Find-Algorithmus. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!