Implementasi Pohon Merentang Minimum Dalam Menentukan Prioritas Pemeliharaan Jalur Jalan Kota Dengan Biaya Minimal

Abstract

Abstrak

Penelitian ini bertujuan bagaimana mengimplemtasikan algoritma pohon merentang minimum (Minimum Spanning Tree disingkat  MST)   dalam hal ini algoritma prim, kruskal dan brute force kedalam sebuah program aplikasi dengan bahasa pemrograman Visual Basic. Program ini berfungsi untuk menentukan solusi terbaik dengan biaya minimal dalam  pencarian jalur prioritas dalam pemeliharaan jalan-jalan utama kota. Peta jalan utama kota diabstraksikan kedalam graf bentuk matriks ketetanggaan, yang menggunakan teknik pembobotan jalan secara multi criteria weight. Selain itu yang ingin diukur adalah kompleksitas waktu algoritma MST, apakah sudah sesuai dengan dasar teori laju pertumbuhan notasi big O  atau tidak?. Penelitian ini kami lakukan di kota Makassar, dengan melakukan 2 tahapan; pengujian program algoritma MST yaitu validasi dan pengujian program,  validasi program adalah uji coba beberapa matriks graf terhubung lengkap Kemudian pengujian program  MST masalah perbaikan jalan dengan memasukkan graf matriks data biaya pemeliharan jalan dengan keluaran  berupa pohon merentang minimum matriks data pemeliharaan jalan kota, dan daftar nama jalan-jalan kota MST.Hasil penelitian ini menunjukkan bahwa pengujian program sudah sesuai dengan algoritma MST, selain itu terlihat bahwa algoritma prim, lebih efisien dibanding kruskal, sedangkan brute force tidak efisien dibandingkan dengan prim dan kruskal.

Kata kunci: Graf, full connected graf, minimum spanning tree, matriks ketetanggaan, algoritma prim, kruskal, dan brute force.