Page 7 - Bahan Ajar Algoritma Prim dan Kruskal New
P. 7
MENGENAL ALGORITMA PRIM DAN KRUSKAL
Algoritma prim dan kruskal merupakan kedua jenis algoritma
yang dapat digunakan untuk mencari pohon rentang minimum pada
sebuah graf. Banyak sekali masalah yang dapat diselesaikan dengan
memodelkan suatu permasalahan tersebut ke dalam graf kemudian
diselesaikan dengan menentukan pohon merentang minimum.
Contohnya mencari rute terpendek, biaya termurah, tenaga seminimal
mungkin dalam pembagunan jalan, jaringan telepon kabel, maupun
jaringan listrik. Dalam pencarian pohon rentang minimum di sebuah
graf, algoritma prim berorientasi pada titik/ simpul, sedangkan
algoritma kruskal berorientasi pada bobot sisi graf. Meski ada
perbedaan pada orientasi akan tetapi kedua algoritma tersebut mampu
memberikan solusi yang sama.
A. Pemecahan Masalah Menggunakan Algoritma Prim
Permasalahan
Suatu perusahaan PDAM akan melakukan pendistribusian air bersih ke
sebuah perumahan. Pendistribusian PDAM ini sangat
mempertimbangkan efisiensi waktu, biaya dan rute. Untuk itu
1
