Penggabungan tahap dan pemampatan laluan dalam algoritma pencarian kesatuan

Algoritma yang dipanggil set pencarian kesatuan (atau set berpisah) bertanggungjawab untuk mengekalkan set yang berbeza dan menyediakan operasi untuk mengesahkan keahlian dalam set dan menggabungkan set bersama-sama. Ia mengendalikan operasi kesatuan dan carian dengan mahir, yang penting untuk mengekalkan maklumat sambungan semasa antara elemen.

Tatabahasa

Untuk kejelasan, mari kita fahami sintaks kaedah yang akan kita gunakan dalam contoh kod berikut.

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

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

Algoritma

Algoritma carian kesatuan terdiri daripada dua operasi asas - kesatuan dan carian. Operasi kesatuan menggabungkan dua set, dan operasi carian menentukan elemen perwakilan set. Dengan menggunakan operasi carian kesatuan secara berulang, kami boleh membina struktur data carian kesatuan yang cekap.

Bersatu mengikut tahap

Teknik sambung demi peringkat digunakan untuk mengoptimumkan operasi sambung dengan memastikan pokok yang lebih kecil sentiasa melekat pada akar pokok yang lebih besar. Pendekatan ini menghalang pokok daripada menjadi terlalu tidak seimbang, mengakibatkan operasi carian tidak cekap.

Algoritma penyatuan mengikut tahap adalah seperti berikut -

• Cari wakil (unsur akar) bagi set yang mengandungi unsur x dan y.

• Kalau wakil rakyat pun sama balik.

• Jika tahap wakil x lebih besar daripada tahap wakil y, jadikan wakil y menunjuk kepada wakil x dan kemas kini tahap wakil x.

• Jika tidak, buat wakil x menunjuk kepada wakil y dan kemas kini kedudukan wakil y jika perlu.

Mampatan laluan

Mampatan laluan ialah satu lagi teknik pengoptimuman yang mengurangkan ketinggian pepohon dalam struktur data pertanyaan. Tujuannya adalah untuk meratakan laluan semasa operasi mencari, dengan itu menyediakan laluan yang lebih pendek untuk operasi seterusnya.

• Algoritma pemampatan laluan adalah seperti berikut -

• Cari wakil (unsur akar) bagi set yang mengandungi unsur x.

• Apabila melintasi laluan dari x ke wakilnya, buat setiap elemen yang dilawati menghala terus kepada wakil.

Kaedah

Sekarang kita memahami konsep asas kesatuan peringkat dan pemampatan laluan, mari kita bincangkan dua cara berbeza untuk melaksanakan algoritma carian kesatuan dalam C++.

Kaedah 1: Pelaksanaan berasaskan tatasusunan

Dalam kaedah ini, kami mewakili setiap koleksi sebagai tatasusunan. Nilai pada setiap indeks mewakili elemen induk elemen. Pada mulanya, setiap elemen ialah induknya sendiri, menunjukkan bahawa ia merupakan wakil koleksinya.

Algoritma

• Mari kita mulakan proses pemulaan tatasusunan induk. Setiap elemen akan diberikan elemen induknya sendiri.

• Gunakan pemampatan laluan untuk melaksanakan operasi carian.

• Gunakan Kesatuan mengikut Pangkat untuk melaksanakan operasi Kesatuan.

Contoh

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

Output

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

Kaedah 2: Pelaksanaan berasaskan pokok

Untuk menerangkan koleksi dalam kajian kami, kami menggunakan pendekatan berasaskan pokok. Setiap item dalam kumpulan dikaitkan dengan nod induk masing-masing dan kami menentukan nod akar untuk mewakili koleksi khusus tersebut.

Algoritma

• Mulakan tatasusunan induk di mana setiap elemen ialah induknya sendiri.

• Gunakan mampatan laluan dan lintasan pokok rekursif untuk melaksanakan operasi carian.

• Gunakan Kesatuan mengikut Pangkat untuk melaksanakan operasi Kesatuan.

• Kod boleh laku yang lengkap

Contoh

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

Output

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

Kesimpulan

Ringkasnya, kesatuan hierarki dan pemampatan laluan ialah teknologi utama dalam algoritma carian kesatuan. Mereka mengoptimumkan operasi kesatuan dan carian masing-masing, menghasilkan prestasi yang lebih baik dan pengurusan maklumat sambungan yang cekap. Dengan melaksanakan teknik ini dalam C++, kami boleh menyelesaikan masalah yang berkaitan dengan set, ketersambungan dan graf dengan cekap.

Untuk meringkaskan, kami memperkenalkan sintaks, algoritma langkah demi langkah dan menyediakan dua contoh kod boleh laku C++ sebenar. Dengan memahami dan menggunakan pemampatan penyatuan dan laluan mengikut kedudukan, anda boleh meningkatkan kemahiran algoritma anda dan menyelesaikan masalah kompleks dengan lebih cekap.

Atas ialah kandungan terperinci Penggabungan tahap dan pemampatan laluan dalam algoritma pencarian kesatuan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!