Kod Java untuk melaksanakan algoritma Kruskal

Algoritma Kruskal

Algoritma Kruskal ialah algoritma tamak yang digunakan untuk menyelesaikan masalah pokok rentang minimum. Pokok rentang minimum ialah pokok rentang dengan jumlah pemberat tepi terkecil dalam graf tidak terarah yang disambungkan. Algoritma Kruskal memilih tepi mengikut tertib daripada pemberat tepi yang kecil ke yang besar Apabila tepi yang dipilih tidak membentuk kitaran, ia ditambah pada pokok rentang. Proses pelaksanaan khusus adalah seperti berikut:

• Isih semua tepi mengikut pemberat tepi dari kecil ke besar.

• Pilih tepi secara bergilir-gilir Jika kedua-dua titik hujung tepi yang dipilih tidak berada dalam komponen yang disambungkan yang sama, tambahkan tepi ini pada pepohon rentang minimum dan gabungkan kedua-dua titik hujung ke dalam sambungan yang sama. komponen.

• Sehingga pokok rentang minimum mengandungi semua bucu dalam graf. Kelebihan algoritma

ialah ia hanya perlu memberi perhatian kepada berat tepi dan tiada kaitan dengan darjah bucu, jadi ia juga boleh menunjukkan prestasi yang lebih baik dalam graf padat. Pada masa yang sama, algoritma Kruskal juga mempunyai kebolehskalaan yang baik dan boleh mengendalikan masalah hutan rentang minimum dalam graf berwajaran dengan mudah.

Proses pelaksanaan

• Isih semua tepi mengikut berat dari kecil ke besar; kedua-dua nod yang disambungkan oleh tepi ini tidak berada dalam komponen yang disambungkan yang sama, tambahkan tepi ini pada pokok spanning dan gabungkan kedua-dua nod menjadi satu komponen yang disambungkan; berada dalam komponen bersambung yang sama, pokok yang dihasilkan pada masa ini ialah pokok rentang minimum.

• Semasa proses pelaksanaan, set pencarian kesatuan biasanya digunakan untuk mengekalkan ketersambungan bagi meningkatkan kecekapan.

Pelaksanaan Kod

• Fungsi menggunakan kaedah isihan kelas Arrays untuk mengisih tepi mengikut beratnya daripada kecil ke besar. Kemudian, fungsi merentasi tepi yang diisih dalam urutan, dan untuk setiap tepi, menggunakan fungsi cari untuk mencari nod punca set di mana src dan destnya terletak. Jika nod akar berbeza, ini bermakna kedua-dua set tidak disambungkan dan boleh digabungkan, dan tepi ditambah pada tatasusunan hasil pokok rentang minimum. Akhir sekali, fungsi merentasi tatasusunan hasil pokok rentang minimum dan mengeluarkan titik permulaan, titik akhir dan berat setiap tepi.

Dalam pelaksanaan ini, kaedah mencari set dengan pantas digunakan, iaitu menggunakan carian kesatuan untuk mencapainya. Setiap nod mempunyai tatasusunan induk, di mana induk[i] mewakili nod induk nod i Jika induk[i] == -1, nod i ialah nod akar. Apabila mencari set di mana nod terletak, jika nod induk nod semasa ialah -1, ini bermakna nod ialah nod akar dan dikembalikan secara langsung, jika tidak, set di mana nod induk berada dicari secara rekursif . Apabila menggabungkan dua koleksi, cari nod akar dua koleksi untuk digabungkan, dan tetapkan nod induk satu nod akar kepada indeks nod akar yang lain, iaitu, gabungkan nod akar satu koleksi di bawah nod akar koleksi yang lain.

Kerumitan masa algoritma Kruskal yang dilaksanakan dengan cara ini ialah O(ElogE), di mana E mewakili bilangan tepi dalam graf, dan kos masa utama terletak pada proses mengisih tepi. Kerumitan ruang ialah O(V+E), di mana V mewakili bilangan bucu dalam graf Overhed ruang utama adalah untuk menyimpan tepi dan tatasusunan induk.

Atas ialah kandungan terperinci Kod Java untuk melaksanakan algoritma Kruskal. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!