Pertama, mari kita lihat dua gambar kompresi jalur:
Set union-find adalah struktur data yang sangat rumit dan praktis, yang terutama digunakan untuk menangani masalah gabungan dari beberapa set yang tidak mengikat. Beberapa kegunaan umum termasuk menghubungkan subgraph, algoritma Kruskal untuk menemukan pohon spanning minimum, dan leluhur paling umum (LCA).
Saat menggunakan dan mencari satu set, pertama -tama akan ada satu set set dinamis disjoint S = {S 1, S 2, ⋯, S K}, yang umumnya menggunakan bilangan bulat untuk mewakili elemen dalam set.
Setiap set dapat berisi satu atau lebih elemen, dan elemen dalam set dipilih sebagai perwakilan. Tidak penting untuk peduli elemen mana yang terkandung dalam setiap set, dan tidak penting untuk peduli elemen mana yang dipilih sebagai perwakilan. Yang kami pedulikan adalah bahwa untuk elemen yang diberikan, kami dapat dengan cepat menemukan set (representasi) di mana elemen ini berada, dan menggabungkan set tempat kedua elemen berada, dan kompleksitas waktu operasi ini konstan.
Ada tiga operasi dasar untuk pemeriksaan dan pengumpulan:
MakeTet: Buat set baru dan pencarian, yang berisi set elemen tunggal.
Unionset (x, y): Menggabungkan set di mana elemen X dan elemen y berada, dan mensyaratkan bahwa set di mana x dan y berada tidak berpotongan, dan jika mereka berpotongan, mereka tidak bergabung.
Temukan (x): Temukan perwakilan set di mana elemen X berada. Operasi ini juga dapat digunakan untuk menentukan apakah dua elemen berada di set yang sama. Bandingkan saja perwakilan mereka masing -masing.
Paket com.dataStructure.union_find; // edisi kelima kami Union-findpublic class Unionfind5 {// peringkat [i] mewakili jumlah lapisan pohon yang diwakili oleh set yang di-root oleh i // dalam kode yang tidak akan memelihara pangkat ini selama pangkat (yaitu nilai peringkat ini bukan nilai layer dari pangkat kami. kedalaman. Itu hanya standar untuk perbandingan peringkat int [] pribadi; private int [] induk; // Parent [i] mewakili simpul induk yang ditunjukkan oleh unsur i-th Count Private Int; // jumlah data // konstruktor public unionfind5 (int count) {rank = new int [count]; induk = int baru [count]; this.count = count; // Inisialisasi, setiap orang tua [i] menunjuk pada dirinya sendiri, menunjukkan bahwa setiap elemen membentuk set sendiri untuk (int i = 0; i <count; i ++) {parent [i] = i; peringkat [i] = 1; }} // Proses pencarian, temukan nomor yang disetel sesuai dengan elemen p // o (h) kompleksitas, h adalah ketinggian pohon private int find (int p) {assert (p> = 0 && p <count); // Path Compression 1 while (p! = Parent [p]) {Parent [p] = Parent [Parent [p]]; p = induk [p]; } return p; // Path Compression 2, Algoritma Rekursif // if (p! = Parent [p]) // Parent [p] = find (Parent [p]); // return Parent [p]; } // Periksa apakah elemen p dan elemen q termasuk dalam kompleksitas set // o (h), h adalah ketinggian pohon boolean publik isconnected (int p, int q) {return find (p) == find (q); } // Gabungkan set ke elemen mana P dan elemen q milik // o (h) kompleksitas, h adalah ketinggian pohon public void elitements (int p, int q) {int proot = find (p); int qroot = find (q); if (proot == qroot) kembali; // menilai arah gabungan berdasarkan jumlah elemen yang berbeda di pohon di mana kedua elemen berada // menggabungkan satu set dengan lebih sedikit elemen ke set dengan lebih banyak elemen jika (peringkat [proot] <peringkat [qroot]) {parent [proot] = qroot; } lain jika (peringkat [qroot] <peringkat [proot]) {induk [qroot] = proot; } else {// peringkat [proot] == peringkat [qroot] induk [proot] = qroot; peringkat [qroot] += 1; // Saat ini, saya mempertahankan nilai peringkat}}}Meringkaskan
Di atas adalah semua penjelasan terperinci dari kode kompresi jalur dalam artikel ini tentang implementasi dan pengumpulan pemrograman Java. Saya harap ini akan membantu semua orang. Teman yang tertarik dapat terus merujuk ke topik terkait lainnya di situs ini. Jika ada kekurangan, silakan tinggalkan pesan untuk menunjukkannya. Terima kasih teman atas dukungan Anda untuk situs ini!