Prof. Dra. Kiki Ariyanti Sugeng, M.Si., Ph.D.

Video ini membahas algoritma Prim dalam Matematika Diskrit, di mana algoritma ini memilih busur dengan bobot minimal dan menyusunnya ke dalam sebuah pohon. Berbeda dengan algoritma Kruskal, pada algoritma Prim busur yang dipilih harus bersisian dengan busur-busur sebelumnya yang sudah dipilih. Langkah-langkah algoritma Prim diilustrasikan melalui contoh grafik dengan pemilihan busur minimal yang bersisian, dan membangun spanning tree tanpa adanya lingkaran. Algoritma Prim menghasilkan spanning tree minimal dengan memilih busur minimal yang terhubung dengan busur yang sudah dipilih sebelumnya.

Satu algoritma yang lain yaitu algoritma PRIM yang mengambil busur dari graf yang bobotnya minimal

Terus pilih bobot IJ yang minimum, tapi disini ada syaratnya,

dia kalau yang pertama ngambil, ambil yang minimum ya,

tapi yang berikutnya adalah yang bersisian dengan busur-busur yang sudah kita ambil.

Kalau yang kruskal tadi kan boleh milih sembarang, kalau sekarang mesti disambungin gitu.

Jadi kita lihat disini langkah pertama itu belum kita ambil apa-apa,

langkah keduanya kayak tadi ya kita ambil EC itu bobotnya 5,

yang berikutnya kita nggak boleh ambil AB seperti yang algoritma kruskal karena dia tidak bersisian sama EC,

maka pilihannya adalah BC, CF, AF atau BE dan ED.

Nah itu kita ambil yang paling kecil mana?

Dalam hal ini DE yang kita ambil, jadi ini DE dengan bobot 11.

Berikutnya lagi langkahnya sama, jadi kita harus ambil busur yang bersisian,

tetap nggak boleh ngambil AB, jadi bolehnya pilihannya adalah BC, BE, AD, kemudian DF dan CF.

Maka kita pilih yang CF karena kita pilih yang CF karena kecil, jadi 12 disini.

Langkah ini kita lanjutkan juga yang harus tersambung,

dalam hal ini kita ambil dan yang terakhir baru boleh ngambil si AB yang bobotnya tadi lebih kecil

tapi tidak terpilih-pilih karena si A itu sudah tersambung dengan B.

Nah ini nanti bobotnya untuk spanning tree-nya kita jumlahkan dari bobot-bobot yang sudah kita ambil.

Untuk algoritma prim bisa kita coba lagi di contoh yang gambar ini,

kemudian pilihan kedua adalah kita cari yang bersisian dengan si HG,

Yang berikutnya lagi kita lihat bahwa yang minimal adalah nilainya 2 disini IC,

tapi karena dia tidak terhubung tidak bersisian kita tidak boleh ambil,

berarti kita pilih yang berikutnya minimal berikutnya disini 4 ada AB ada CF.

Nah yang terhubung adalah CF berarti kita yang pilihnya yang CF.

Nanti kita mau bikin spanning tree ini mesti diingat,

Oke, sekarang 4 sudah yang AB tidak boleh diambil karena dia tidak bersisian,

berarti yang berikutnya lagi adalah 6 bobotnya,

jadi ini bisa kita ambil IG karena terhubung dengan si G,

7 itu ada HI tapi HI nanti akan membentuk lingkaran tidak bisa kita ambil,

Terus yang berikutnya lagi 7 sudah selesai sekarang 8,

yang AH itu langkah berikutnya tidak bisa diambil karena masih ada yang lebih minimal disini,

karena kita sudah ambil tadi si B nya kan bisa dihubungkan ke A,

jadi yang 8 ini tidak bisa kita ambil lagi.

Oke, 8 sudah selesai sekarang bobot minimal berikutnya lagi adalah 9,

kita ambil yang disini 9 dan kita lihat semua simpul sudah terhubung,

kalau mau dicari bobotnya itu kita jumlahkan semua bobot dari busur-busur yang sudah kita pilih tadi.

kalau kruskal itu pilihnya tidak perlu dia bersisian asalkan minimal kita pilih,

nanti akhirnya akan mendapatkan suatu spanning tree.

tapi kemudian kita pilih busur-busur yang bersisian yang juga paling minimal,

jadi belum tentu minimal dari seluruh busur di graph,

tapi yang terhubung dengan busur yang sudah kita pilih.

Dan algoritma prim ini sudah bisa dibuktikan,

dia juga akan menghasilkan spanning tree minimal dari suatu graph berbobot.

dia tetap akan mendapatkan spanning tree yang minimal.