Pengembangan Algoritma Prim untuk Menentukan Minimum Spanning Forest

Hari Sumardi (Universitas Bengkulu)
Afnaria Afnaria (Universitas Islam Sumatera Utara)
Suvriadi Panggabean (Universitas Muhammadiyah Sumatera Utara)

MAJAMATH: Jurnal Matematika dan Pendidikan Matematika
Vol. 4 No. 1 (2021): Vol. 4 No.1 Maret 2021

Minimum spanning tree (MST) merupakan salah satu permasalahan dalam teori graph. MST dari graph G adalah spanning tree dengan total bobot sisi terkecil pada suatu graph berbobot G yang terhubung. Terdapat dua algoritma klasik di dalam MST yakni algoritma Kruskal dan Prim. Kedua algoritma tersebut dapat menghasilkan sebuah MST. Forest merupakan graph yang terdiri dari beberapa tree. Spanning forest dari graph tak terhubung G merupakan forest yang dibangun dari graph G. Minimum spanning forest (MSF) dari graph G merupakan spanning forest dengan total bobot sisi terkecil atas semua spanning forest pada graph G. Pada hasil, penulis menyajikan sebuah algoritma MSF yang dikembangkan dari algoritma Prim.