Perbedaan yang menonjol antara algoritma Prims dan Krushal adalah algoritma Prim menghasilkan pohon merentang minimum mulai dari simpul akar sedangkan algoritma Krushal menghasilkan pohon merentang minimum mulai dari tepi yang paling tidak berbobot.
Algoritma adalah urutan langkah-langkah yang harus diikuti untuk menyelesaikan suatu masalah. Dalam algoritma serakah, kita dapat membuat keputusan dari domain solusi yang diberikan. Ini menemukan solusi optimal lokal dan dapat mengarah pada pencarian solusi yang dioptimalkan secara global. Algoritma Prim dan Krushal adalah dua algoritma serakah. Bila terdapat graf tak berarah dan terhubung (G), pohon merentang adalah pohon yang merentang dan merupakan subgraf dari G. Pohon merentang minimum adalah pohon merentang yang memiliki biaya minimum di antara semua pohon merentang. Hal ini terutama digunakan dalam merancang jaringan. Kedua algoritma ini membantu untuk menemukan pohon merentang minimum.
Topik bahasan kami tentang:
- Apa itu Algoritma Prim – Definisi, Fungsi 2. Apa itu Algoritma Krushal – Definisi, Fungsi 3. Apa Perbedaan Antara Algoritma Prim dan Krushal – Perbandingan Perbedaan Kunci
Istilah Utama
Grafik, Algoritma Krushal, Algoritma Prim, Pohon
Yang perlu anda ketahui tentang Algoritma Prim
Algoritma Prim membantu menemukan pohon merentang minimum dari sebuah graf . Ini menentukan subset dari tepi yang mencakup setiap simpul dari grafik. Ini juga mengurangi jumlah bobot tepi. Juga, algoritma ini dimulai dengan simpul akar dan memeriksa semua simpul yang berdekatan termasuk semua tepi penghubung pada setiap langkah. Selain itu, ia memilih tepi dengan bobot lebih sedikit yang tidak menyebabkan siklus.
Langkah-langkah algoritmanya adalah sebagai berikut.
Langkah 1 – Pilih simpul awal atau simpul akar
Langkah 2 – Ulangi langkah 3 dan 4 sampai ada simpul pinggiran
Langkah 3 – Pilih tepi yang menghubungkan simpul pohon dan simpul tepi yang memiliki bobot minimum
Langkah 4 – Tambahkan tepi yang dipilih dan simpul ke pohon merentang minimum
Yang perlu anda ketahui tentang Algoritma Krushal?
Algoritma Krushal membantu menemukan pohon merentang minimum untuk graf berbobot terhubung. Ini menemukan himpunan bagian dari tepi yang dapat melintasi setiap titik dari grafik. Algoritma ini menemukan solusi optimal pada setiap tahap daripada menemukan optimal global.
Langkah-langkah dari algoritma tersebut adalah sebagai berikut.
Langkah 1- Buat hutan. Setiap grafik hutan adalah pohon yang terpisah. Hutan adalah kumpulan pohon yang terputus-putus. Kita dapat memperolehnya dengan menghapus simpul akar dan tepi yang menghubungkan simpul akar ke simpul tingkat pertama.
Langkah 2- Buat antrian prioritas yang terdiri dari semua tepi grafik.
Langkah 3 – Ulangi langkah 4 dan 5, jika antrian prioritas tidak kosong.
Langkah 4 – Hapus tepi dari antrian prioritas.
Langkah 5 – Jika tepi yang dihasilkan dari langkah 4 menghubungkan dua pohon, tambahkan ke hutan; jika tidak membuang tepi.
Perbedaan Antara Algoritma Prim dan Krushal
Definisi
Algoritma Prim adalah algoritma serakah yang menemukan pohon merentang minimum untuk graf tak berarah berbobot sedangkan algoritma Krushal adalah algoritma pohon merentang minimum yang menemukan tepi dengan bobot terkecil yang menghubungkan dua pohon di hutan. Ini adalah Perbedaan yang menonjol antara algoritma Prims dan Krushal.
Generasi
Selain itu, algoritma Prim menghasilkan pohon merentang minimum mulai dari simpul akar. Namun, algoritma Krushal menghasilkan pohon merentang minimum mulai dari tepi yang paling sedikit berbobot.
Pilihan
Perbedaan lain antara algoritma Prims dan Krushal adalah algoritma Prim memilih simpul akar sedangkan algoritma Krushal memilih tepi terpendek.
Prosedur
Sementara algoritma Prim memilih tepi terpendek yang terhubung ke simpul akar, algoritma Krushal memilih tepi terpendek berikutnya. Ini adalah perbedaan lain antara algoritma Prims dan Krushal.
Kata terakhir
Algoritma Prim dan Krushal membantu menemukan pohon merentang minimum dari sebuah graf. Perbedaan antara algoritma Prims dan Krushal adalah algoritma Prim menghasilkan pohon merentang minimum dimulai dari simpul akar sedangkan algoritma Krushal menghasilkan pohon merentang minimum dimulai dari tepi yang paling sedikit berbobot.
Sumber bacaan:
- “Algoritma Prim – Javatpoint.” www.javatpoint.com, Tersedia di sini . 2. “Algoritma Kruskal – Javatpoint.” www.javatpoint.com, Tersedia di sini . 3. “Pohon – Javatpoint.” www.javatpoint.com, Tersedia di sini . 4. “Algoritma Prim.” Wikipedia, Wikimedia Foundation, 18 November 2018, Tersedia di sini . 5. “Algoritma Kruskal.” Wikipedia, Wikimedia Foundation, 12 Des 2018, Tersedia di sini .
Sumber gambar:
- “Algoritma Prim 3” Oleh Alexander Drichel, Stefan Birkner – Karya sendiri (CC BY-SA 3.0) melalui Commons Wikimedia 2. “MST kruskal en” Oleh Schulllz – Karya sendiri (CC BY-SA 3.0) melalui Commons Wikimedia
