Perbedaan Antara Kruskal dan Prim

Kruskal vs Prim

Dalam ilmu komputer, algoritma Prim's dan Kruskal adalah algoritma serakah yang menemukan pohon rentang minimum untuk grafik tanpa arah tertimbang yang terhubung. Pohon spanning adalah subgraf grafik sedemikian rupa sehingga setiap simpul grafik dihubungkan oleh 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

Algoritma 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. Ia ditemukan kembali oleh Edsger Dijkstra pada tahun 1959. Algoritma ini dapat dinyatakan dalam tiga langkah kunci;

Diberikan grafik terhubung dengan n node dan masing-masing berat masing-masing tepi,

1. Pilih node sewenang-wenang dari grafik dan tambahkan ke pohon T (yang akan menjadi node pertama)

2. Pertimbangkan bobot masing-masing tepi yang terhubung ke node di pohon dan pilih minimum. Tambahkan tepi dan simpul di ujung 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 tunggal dan berkembang dari simpul itu ke depan 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 proses 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 sedikit dari seluruh 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, algoritma dimulai dengan tepi paling sedikit 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 menginisialisasi dengan sebuah node, sedangkan algoritma Kruskal memulai dengan sebuah edge.

• Algoritma Prim merentang dari satu simpul ke simpul lainnya sementara algoritma Kruskal memilih tepi sedemikian rupa sehingga posisi tepi tidak didasarkan pada langkah terakhir.

• Dalam algoritma prim, grafik harus berupa grafik yang terhubung sementara Kruskal's dapat berfungsi pada grafik yang terputus juga.

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