Algoritma Prim

Bayangkan memasang kabel dari pembangkit listrik: Anda menghubungkan kota terdekat dulu, lalu kota mana pun yang paling dekat dengan tempat yang sudah terhubung, dan seterusnya. Itulah algoritma Prim, dan hasilnya selalu jaringan termurah yang mungkin.

Graf dengan pohon yang tumbuh dari satu simpul, simpul-simpul yang menunggu di sekitarnya dengan sisi terbaik digambar putus-putus, dan daftar simpul yang menunggu di bawahnya
Graf dengan pohon yang tumbuh dari satu simpul, simpul-simpul yang menunggu di sekitarnya dengan sisi terbaik digambar putus-putus, dan daftar simpul yang menunggu di bawahnya

Idenya

Pohon merentang minimum menghubungkan setiap simpul graf berbobot dengan total panjang sisi sekecil mungkin. Algoritma Prim membangunnya dengan menumbuhkan satu pohon ke luar dari awal. Pohon itu tidak pernah terpecah: di setiap langkah, tepat satu simpul baru bergabung, lewat sisi terpendek yang keluar dari pohon.

Langkah demi langkah

Masukkan simpul awal ke pohon. Untuk setiap simpul di luar pohon, simpan sisi terbaiknya: sisi terpendeknya ke simpul mana pun di pohon. Lalu ulangi: pilih simpul luar yang sisi terbaiknya paling pendek, tambahkan ke pohon bersama sisi itu, dan periksa sisi-sisinya. Tetangga di luar pohon yang kini bisa dicapai lewat sisi yang lebih pendek mendapat sisi itu sebagai sisi terbaik barunya. Berhenti saat semua simpul ada di pohon.

Contoh

Ambil sisi A–B dengan panjang 1, B–C 2, A–C 3, C–D 4, dan B–D 5, lalu mulai dari A. Sisi-sisi A memberi B sisi terbaik 1 dan C sisi terbaik 3. B paling dekat, jadi B bergabung lewat A–B; sisi-sisinya memperbaiki C menjadi 2 dan memberi D 5. C bergabung lewat B–C, dan sisinya C–D memperbaiki D menjadi 4. Akhirnya D bergabung lewat C–D. Pohon A–B, B–C, C–D punya total panjang 1 + 2 + 4 = 7.

Mengapa benar

Di setiap langkah, simpul terbagi menjadi dua kelompok: yang di dalam pohon dan yang di luar. Sifat potong menyatakan bahwa sisi terpendek antara dua kelompok seperti itu selalu termasuk dalam suatu pohon merentang minimum. Prim selalu menambahkan tepat sisi itu, jadi pohon yang sudah dibangunnya selalu bisa dilengkapi menjadi pohon merentang minimum, dan saat semua simpul sudah bergabung, pohon itu adalah pohon merentang minimum.

Sejarah dan kecepatan

Matematikawan Ceko Vojtěch Jarník menerbitkan algoritma ini pada 1930. Robert Prim menemukannya kembali di Bell Labs pada 1957, dan Edsger Dijkstra sekali lagi pada 1959. Dengan simpul yang menunggu dalam binary heap, kerjanya tumbuh sebanding E log V untuk V simpul dan E sisi; dengan array biasa sekitar V², yang lebih baik bila hampir setiap pasang simpul terhubung. Dengan Fibonacci heap kerjanya E + V log V.

Jelajahi

Buka aplikasinya, klik simpul untuk mulai dari sana, lalu tekan Langkah. Simpul di dalam pohon berwarna hijau, simpul yang menunggu berwarna biru, dan sisi terbaik tiap simpul yang menunggu digambar putus-putus. Simpul yang menunggu didaftar di bawah graf dengan panjang sisi terbaiknya, yang terpendek lebih dulu: yang pertama bergabung berikutnya. Mulailah dari simpul yang berbeda dan lihat urutannya berubah sementara totalnya tetap sama.

Pertanyaan yang sering diajukan

Apa bedanya algoritma Prim dan algoritma Dijkstra?

Keduanya menumbuhkan wilayah dari awal dengan antrean prioritas. Prim mengurutkan simpul yang menunggu menurut panjang satu sisi terbaiknya ke pohon; Dijkstra menurut seluruh jaraknya dari awal. Prim menghasilkan pohon merentang minimum, Dijkstra pohon jalur terpendek.

Apakah algoritma Prim bisa dipakai dengan panjang sisi negatif?

Ya. Tidak seperti algoritma Dijkstra, Prim hanya membandingkan sisi satu sama lain, jadi panjang negatif tidak menimbulkan masalah: algoritma ini tetap menemukan pohon merentang dengan total terkecil.

Bagaimana jika grafnya tidak terhubung?

Maka algoritma Prim berhenti setelah mencapai semua simpul yang bisa dicapainya: hasilnya pohon merentang minimum untuk bagian yang memuat simpul awal saja. Menjalankannya lagi dari simpul yang belum dicapai menghasilkan hutan merentang minimum.

Mana yang lebih baik, algoritma Prim atau Kruskal?

Tidak ada yang selalu menang. Prim cocok untuk graf padat dan graf yang disimpan sebagai daftar tetangga; Kruskal cocok untuk graf jarang yang diberikan sebagai daftar sisi. Keduanya menemukan pohon dengan total panjang yang sama.

Siap mencobanya?

Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.

Coba algoritma Prim