Kruskal vs Prim
Dalam ilmu komputer, algoritma Prim dan Kruskal adalah algoritma serakah yang menemukan pohon merentang minimum untuk graf tak berarah berbobot terhubung. Spanning tree adalah subgraf dari graf sedemikian rupa sehingga setiap simpul dari graf tersebut dihubungkan oleh sebuah jalur, yang merupakan pohon. Setiap spanning tree memiliki bobot, dan bobot/biaya minimum yang mungkin dari semua spanning tree adalah minimum spanning tree (MST).
Lebih lanjut tentang Algoritma Prim
Algoritme ini dikembangkan oleh matematikawan Ceko Vojtěch Jarník pada tahun 1930 dan kemudian secara independen oleh ilmuwan komputer Robert C. Prim pada tahun 1957. Ditemukan kembali oleh Edsger Dijkstra pada tahun 1959. Algoritma ini dapat dinyatakan dalam tiga langkah utama;
Mengingat graf terhubung dengan n node dan bobot masing-masing sisi, 1. Pilih simpul sembarang 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 hapus tepi dari grafik. (Pilih salah satu jika ada dua atau lebih minimum)
3. Ulangi langkah 2, hingga n-1 tepi ditambahkan ke pohon.
Dalam metode ini, pohon dimulai dengan satu simpul arbitrer dan berkembang dari simpul itu dan seterusnya dengan setiap siklus. Oleh karena itu, agar algoritme berfungsi dengan baik, graf tersebut harus berupa graf terhubung. Bentuk dasar dari algoritma Prim memiliki kompleksitas waktu O(V2).
Lebih lanjut tentang Algoritma Kruskal
Algoritme yang dikembangkan oleh Joseph Kruskal muncul dalam prosiding American Mathematical Society pada tahun 1956. Algoritma Kruskal juga dapat dinyatakan dalam tiga langkah sederhana.
Mengingat grafik dengan n node dan bobot masing-masing tepi, 1. Pilih busur dengan bobot terkecil dari keseluruhan grafik dan tambahkan ke pohon dan hapus dari grafik.
2. Dari yang tersisa pilih tepi yang paling tidak berbobot, dengan cara yang tidak membentuk siklus. Tambahkan tepi ke pohon dan hapus dari grafik. (Pilih salah satu jika ada dua atau lebih minimum)
3. Ulangi proses pada langkah 2.
Dalam metode ini, algoritme dimulai dengan tepi berbobot terkecil 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 sebuah node, sedangkan algoritma Kruskal dimulai dengan sebuah edge.
• Algoritma Prim merentang dari satu node ke node lainnya sedangkan algoritma Kruskal memilih edge sedemikian rupa sehingga posisi edge tidak didasarkan pada langkah terakhir.
• Dalam algoritma prim, graf harus berupa graf terhubung sedangkan Kruskal juga dapat berfungsi pada graf tak terhubung.
• Algoritma Prim memiliki kompleksitas waktu O(V2), dan kompleksitas waktu Kruskal adalah O(logV).
