Pengenalan kepada struktur data set terputus atau algoritma pencarian kesatuan

Struktur maklumat set berpisah, juga dikenali sebagai algoritma carian kesatuan, mungkin merupakan konsep asas dalam sains komputer yang menyediakan penyelesaian kepada masalah berkaitan peruntukan dan kaedah rangkaian yang berkesan . Ia amat berharga untuk menyelesaikan masalah yang melibatkan set komponen dan menentukan sambungannya. Dalam artikel ini, kita akan melihat binaan bahasa, algoritma dan dua cara unik untuk melaksanakan struktur maklumat set berpisah dalam C++. Kami juga akan menyediakan contoh kod boleh laku sepenuhnya yang menggambarkan kaedah ini.

tatabahasa

Sebelum kita mendalami algoritma, mari biasakan diri kita dengan sintaks yang digunakan dalam contoh kod berikut -

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

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

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

Algoritma

Menggunakan struktur data bercabang boleh menjadi sangat berguna apabila berurusan dengan berbilang koleksi yang tidak berkaitan. Setiap kumpulan individu diberikan wakil tertentu untuk mencirikannya. Titik permulaan melibatkan setiap komponen membentuk set terpencilnya sendiri, yang sepadan dengan wakil masing-masing (yang juga berlaku untuk dirinya sendiri). Dua operasi utama yang dilakukan pada set berpisah ialah kesatuan dan carian.

operasi bersama

• Cari wakil dua set yang anda ingin gabungkan.

• Buat satu perwakilan menunjuk kepada yang lain jika perwakilan berbeza, menggabungkan set dengan berkesan.

• Jika wakil adalah sama, set telah digabungkan dan tiada tindakan lanjut diperlukan.

Cari operasi

• Diberi elemen, cari wakil set yang dimilikinya.

• Ikuti penunjuk induk sehingga ia mencapai nod wakil.

• Kembalikan perwakilan sebagai hasilnya.

Kaedah 1: Penggabungan berasaskan kedudukan dan pemampatan laluan

Cara yang berkesan untuk melaksanakan struktur data set bercabang adalah dengan menggunakan teknik pemampatan penyatuan dan laluan mengikut kedudukan.

Dalam kaedah ini, setiap koleksi mempunyai kedudukan yang berkaitan, yang pada mulanya ditetapkan kepada 0.

Apabila melakukan operasi kesatuan antara dua set, set yang lebih tinggi diberi keutamaan dan set yang lebih rendah digabungkan. Jika dua set mempunyai pangkat yang sama, seseorang mesti sewenang-wenangnya memilih set mana yang mengandungi siapa. Dalam kedua-dua kes, setelah digabungkan menjadi set baharu, kedudukannya meningkat sebanyak 1. Selain itu, untuk mempercepatkan operasi carian dan mengurangkan kerumitan masa, pemampatan laluan membantu meratakan struktur pokok semasa operasi ini.

Terjemahan bahasa Cina bagi

Contoh

ialah:

Contoh

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

Output

0
2

Kaedah 2: Penggabungan berasaskan saiz dengan saiz dan mampatan laluan

Cara lain untuk menangani struktur data set terputus-putus adalah dengan menggunakan teknik mampatan gabungan mengikut saiz dan laluan.

• Dalam kaedah ini, setiap koleksi mempunyai saiz yang berkaitan, yang pada mulanya ditetapkan kepada 1.

• Dalam operasi kesatuan, set yang lebih kecil digabungkan menjadi set yang lebih besar.

• Saiz set keputusan akan dikemas kini dengan sewajarnya.

• Gunakan mampatan laluan semasa operasi mencari untuk meratakan struktur pokok, sama seperti kaedah sebelumnya.

Terjemahan bahasa Cina bagi

Contoh

ialah:

Contoh

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

Output

0
2

KESIMPULAN

Struktur data set bercabang atau algoritma carian kesatuan ialah alat yang berkuasa untuk menyelesaikan masalah yang melibatkan set dan ketersambungan. Artikel ini mengkaji secara meluas sintaks struktur data set berpisah C++ dan algoritmanya. Untuk memanjangkan pemahaman kami, kami menyediakan dua pendekatan unik kepada pembaca - gabungan berasaskan kedudukan digabungkan dengan pemampatan laluan dan penyatuan berasaskan saiz melalui pemampatan saiz tambah laluan. Dengan memahami dan melaksanakan kaedah ini, anda boleh menyelesaikan pelbagai masalah dengan berkesan yang memerlukan penjejakan set bercabang.

Atas ialah kandungan terperinci Pengenalan kepada struktur data set terputus atau algoritma pencarian kesatuan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!