Page 7 - E-LKM Algoritma Prim dan Kruskal

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.

1