Saya bertanya-tanya kapan kita harus menggunakan algoritma Prim dan kapan Kruskal menemukan pohon spanning minimum? Keduanya memiliki logika yang mudah, kasus terburuk yang sama, dan satu-satunya perbedaan adalah implementasi yang mungkin melibatkan struktur data yang sedikit berbeda. Jadi apa faktor penentu?
Gunakan algoritma Prim ketika Anda memiliki grafik dengan banyak sisi.
Untuk grafik dengan V sudut E tepi, algoritma Kruskal berjalan dalam waktu O (E log V) dan algoritma Prim dapat berjalan dalam waktu diamortisasi O (E + V log V) , jika Anda menggunakan Fibonacci Heap .
Algoritma Prim secara signifikan lebih cepat dalam batas ketika Anda memiliki grafik yang sangat padat dengan lebih banyak tepi daripada simpul. Kruskal berkinerja lebih baik dalam situasi khusus (grafik jarang) karena menggunakan struktur data yang lebih sederhana.
Saya menemukan utas yang sangat bagus di internet yang menjelaskan perbedaannya dengan cara yang sangat mudah: http://www.thestudentroom.co.uk/showthread.php?t=232168 .
Algoritma Kruskal akan menumbuhkan solusi dari tepi termurah dengan menambahkan tepi termurah berikutnya, asalkan tidak menciptakan siklus.
Algoritma Prim akan menumbuhkan solusi dari titik acak dengan menambahkan titik termurah berikutnya, titik yang saat ini tidak ada dalam solusi tetapi terhubung ke sana oleh tepi termurah.
Terlampir di sini adalah lembar menarik tentang topik itu.
Jika Anda menerapkan Kruskal dan Prim, masing-masing dalam bentuk optimal: dengan gabungan serikat dan tumpukan finbonacci, maka Anda akan mencatat bagaimana Kruskal mudah diterapkan dibandingkan dengan Prim.
Prim lebih sulit dengan tumpukan fibonacci terutama karena Anda harus mempertahankan tabel pembukuan untuk merekam tautan dua arah antara simpul grafik dan simpul tumpukan. Dengan Union Find, itu kebalikannya, strukturnya sederhana dan bahkan dapat menghasilkan langsung mst tanpa biaya tambahan.
sumber
V-1.Saya tahu bahwa Anda tidak meminta ini, tetapi jika Anda memiliki lebih banyak unit pemrosesan, Anda harus selalu mempertimbangkan algoritma Borůvka , karena itu mungkin mudah diparalelkan - karenanya ia memiliki keunggulan kinerja dibandingkan dengan algoritma Kruskal dan Jarník-Prim.
sumber
Kruskal dapat memiliki kinerja yang lebih baik jika ujungnya dapat diurutkan dalam waktu linier, atau sudah diurutkan.
Prim lebih baik jika jumlah tepi ke simpul tinggi.
sumber
Kruskal waktu kompleksitas kasus terburuk adalah O (E log E) , ini karena kita perlu mengurutkan tepi. Prim waktu kompleksitas kasus terburuk adalah O (E log V) dengan antrian prioritas atau bahkan lebih baik, O (E + V log V) dengan Fibonacci Heap . Kita harus menggunakan Kruskal ketika grafiknya tipis, jumlah tepi yang kecil, seperti E = O (V), ketika tepinya sudah diurutkan atau jika kita bisa mengurutkannya dalam waktu linier. Kita harus menggunakan Prim ketika grafik padat, yaitu jumlah tepi tinggi, seperti E = O (V²).
sumber
Jika kita menghentikan algoritme dalam algoritma prim tengah selalu menghasilkan pohon terhubung, tetapi kruskal di sisi lain dapat memberikan pohon atau hutan yang terputus
sumber
Salah satu aplikasi penting dari algoritma Kruskal adalah dalam pengelompokan tautan tunggal .
Pertimbangkan n simpul dan Anda memiliki grafik yang lengkap. Untuk memperoleh kelompok-kelompok n dari titik-titik tersebut. Algoritma run Kruskal pada tepi n- (k-1) pertama dari kumpulan tepi yang diurutkan. Anda mendapatkan k-cluster grafik dengan maksimum jarak.
sumber
Waktu terbaik untuk Kruskal adalah O (E logV). Untuk Prim yang menggunakan tumpukan fib, kita bisa mendapatkan O (E + V lgV). Oleh karena itu pada grafik yang padat, Prim jauh lebih baik.
sumber
Prim lebih baik untuk grafik yang lebih padat, dan dalam hal ini kita juga tidak perlu terlalu memperhatikan siklus dengan menambahkan keunggulan, karena kita terutama berurusan dengan node. Prim lebih cepat daripada Kruskal dalam hal grafik kompleks.
sumber
Dalam Algoritma kruskal kita memiliki jumlah sisi dan jumlah simpul pada grafik yang diberikan tetapi pada setiap sisi kita memiliki beberapa nilai atau bobot atas nama yang kita dapat menyiapkan grafik baru yang tidak boleh siklik atau tidak menutup dari sisi manapun Sebagai contoh
grafik seperti ini _____________ | | | | | | | __________ | | Beri nama untuk titik mana saja a, b, c, d, e, f.
sumber