ANALISIS TRADE-OFF WAKTU EKSEKUSI DAN PENGGUNAAN MEMORI ALGORITMA PRIM, KRUSKAL, DAN BORŮVKA PADA GRAF TSPLIB

Abstract

Minimum spanning tree merupakan konsep penting dalam perancangan jaringan berbiaya minimum, dengan algoritma Prim, Kruskal, dan Borůvka sebagai tiga pendekatan klasik yang paling sering digunakan dalam literatur teori graf dan optimasi jaringan. Penelitian ini memfokuskan analisis pada trade-off antara waktu eksekusi dan penggunaan memori ketiga algoritma tersebut pada graf lengkap berbobot yang dibangun dari tiga instance TSPLIB, yaitu pr264, att532, dan rat575, yang direpresentasikan sebagai graf Euclidean dan pseudo-Euclidean berskala menengah. Setiap instance dikonversi menjadi graf tak berarah berbobot dan diproses oleh algoritma Prim, Kruskal, dan Borůvka dalam satu kerangka pemrograman yang seragam, dengan pengukuran waktu eksekusi rata-rata, simpangan baku, koefisien variasi, rata-rata serta puncak penggunaan memori, dan verifikasi bobot MST terhadap nilai referensi. Hasil menunjukkan bahwa pada pr264 dan att532 seluruh algoritma menghasilkan bobot MST identik dan optimal, sedangkan pada rat575 ketiganya menghasilkan bobot sedikit di atas nilai referensi dengan deviasi relatif sama, yang mengindikasikan adanya isu numerik terkait definisi jarak dan pembulatan di TSPLIB. Dari sisi waktu, algoritma Kruskal secara konsisten menjadi algoritma tercepat pada semua dataset dengan TimeRatio = 1, sementara Prim dan Borůvka dapat mencapai lebih dari 20 dan 40 kali lebih lambat pada rat575, sedangkan dari sisi memori, Borůvka selalu menjadi algoritma paling hemat memori dengan MemoryRatio = 1 dan Prim tercatat hingga lebih dari 50 kali lebih boros memori pada dataset terbesar. Temuan ini menegaskan bahwa untuk graf lengkap berbasis TSPLIB, algoritma Kruskal merupakan pilihan utama ketika kecepatan eksekusi menjadi prioritas, algoritma Borůvka sesuai untuk skenario dengan keterbatasan memori atau potensi paralelisasi, sedangkan algoritma Prim lebih tepat diposisikan sebagai baseline klasik untuk pembandingan teoretis dan eksperimen algoritma MST