Perbedaan antara Kruskal dan Prim
Kruskal vs Prim
Dalam Ilmu Komputer, Algoritma Prim dan Kruskal adalah algoritma serakah yang menemukan pohon spanning minimum untuk grafik tidak terarah tertimbang yang terhubung. Pohon spanning adalah subgraph dari grafik sehingga setiap simpul grafik dihubungkan oleh jalur, yang merupakan pohon. Setiap spanning tree memiliki bobot, dan minimum yang memungkinkan/biaya semua pohon spanning adalah minimum spanning tree (MST).
Lebih lanjut tentang algoritma Prim
Algoritma ini dikembangkan oleh ahli matematika Ceko Vojtěch Jarník pada tahun 1930 dan kemudian secara independen oleh ilmuwan komputer Robert C. Prim pada tahun 1957. Itu ditemukan kembali oleh Edsger Dijkstra pada tahun 1959. Algoritma dapat dinyatakan dalam tiga langkah kunci;
Mengingat grafik yang terhubung dengan n node dan masing -masing berat masing -masing tepi,
1. Pilih simpul sewenang -wenang dari grafik dan tambahkan ke pohon t (yang akan menjadi simpul pertama)
2. Pertimbangkan bobot setiap tepi yang terhubung ke node di pohon dan pilih minimum. Tambahkan tepi dan simpul di ujung lain dari pohon T dan lepaskan tepi dari grafik. (Pilih apapun jika ada dua atau lebih minimum)
3. Ulangi Langkah 2, sampai tepi N-1 ditambahkan ke pohon.
Dalam metode ini, pohon dimulai dengan satu simpul sewenang -wenang dan mengembang dari simpul itu dan seterusnya dengan setiap siklus. Oleh karena itu, agar algoritma berfungsi dengan baik, grafik harus menjadi grafik yang terhubung. Bentuk dasar algoritma prim memiliki kompleksitas waktu O (v2).
Lebih lanjut tentang algoritma Kruskal
Algoritma yang dikembangkan oleh Joseph Kruskal muncul dalam Prosiding American Mathematical Society pada tahun 1956. Algoritma Kruskal juga dapat diekspresikan dalam tiga langkah sederhana.
Mengingat grafik dengan n node dan masing -masing berat masing -masing tepi,
1. Pilih busur dengan bobot paling sedikit dari seluruh grafik dan tambahkan ke pohon dan hapus dari grafik.
2. Dari yang tersisa, pilih ujung yang paling tertimbang, dengan cara yang tidak membentuk siklus. Tambahkan tepi ke pohon dan hapus dari grafik. (Pilih apapun jika ada dua atau lebih minimum)
3. Ulangi prosesnya di Langkah 2.
Dalam metode ini, algoritma dimulai dengan tepi tertimbang paling sedikit dan terus memilih setiap tepi pada setiap siklus. Oleh karena itu, dalam algoritma grafik tidak perlu dihubungkan. Algoritma Kruskal memiliki kompleksitas waktu O (logv)
Apa perbedaan antara algoritma Kruskal dan Prim?
• Algoritma Prim diinisialisasi dengan node, sedangkan algoritma Kruskal dimulai dengan tepi.
• Algoritma Prim dari satu simpul ke satu node sementara algoritma Kruskal memilih tepi dengan cara yang posisi tepi tidak didasarkan pada langkah terakhir.
• Dalam algoritma Prim, grafik harus berupa grafik yang terhubung sementara Kruskal dapat berfungsi pada grafik yang terputus juga.
• Algoritma Prim memiliki kompleksitas waktu O (V2), dan kompleksitas waktu Kruskal adalah O (logv).
