Perbedaan Antara Kruskal Dan Prim

2024 Pengarang: Mildred Bawerman | [email protected]. Terakhir diubah: 2023-12-16 08:39

Kruskal vs Prim

Dalam ilmu komputer, algoritme Prim dan Kruskal adalah algoritme serakah yang menemukan pohon rentang minimum untuk grafik tak terarah berbobot yang terhubung. Pohon rentang adalah subgraf dari grafik sedemikian rupa sehingga setiap simpul dari grafik dihubungkan oleh sebuah jalur, yaitu sebuah pohon. Setiap pohon bentang memiliki bobot, dan bobot / biaya minimum yang memungkinkan dari semua pohon bentang 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. Algoritme ini ditemukan kembali oleh Edsger Dijkstra pada tahun 1959. Algoritme tersebut dapat dinyatakan dalam tiga langkah kunci;

Diberikan 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 simpul di pohon dan pilih minimum. Tambahkan tepi dan simpul di ujung lain pohon T dan hapus tepi dari grafik. (Pilih salah satu jika ada dua atau lebih minimum)

3. Ulangi langkah 2, sampai n-1 tepi ditambahkan ke pohon.

Dalam metode ini, pohon dimulai dengan satu node arbitrer dan berkembang dari node tersebut dan seterusnya dengan setiap siklus. Oleh karena itu, agar algoritme berfungsi dengan baik, grafik harus berupa grafik yang terhubung. Bentuk dasar dari algoritma Prim memiliki kompleksitas waktu O (V ²).

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.

Diberikan grafik dengan n node dan bobot masing-masing tepi, 1. Pilih busur dengan bobot paling kecil dari keseluruhan grafik dan tambahkan ke pohon dan hapus dari grafik.

2. Dari sisa pilih tepi yang paling sedikit 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, algoritma dimulai dengan sisi yang paling sedikit berbobot dan terus memilih setiap sisi 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 terbentang dari satu node ke node lainnya sedangkan algoritma Kruskal memilih edge dengan cara dimana posisi edge tidak berdasarkan pada langkah terakhir.

• Dalam algoritma prim, graf harus berupa graf terkoneksi sedangkan graf Kruskal dapat berfungsi pada graf terputus juga.

• Algoritma Prim memiliki kompleksitas waktu O (V ²), dan kompleksitas waktu Kruskal adalah O (logV).