<![CDATA[Minimum spanning tree (MST) merupakan konsep penting dalam desain jaringan berbiaya minimum, dengan algoritma Prim, Kruskal, dan Borůvka sebagai tiga pendekatan klasik yang paling sering digunakan. Penelitian ini menganalisis kinerja ketiga algoritma tersebut pada graf lengkap berbobot yang dibangun dari tiga instance TSPLIB, yaitu pr264, att532, dan rat575, untuk memberikan gambaran empiris mengenai kecepatan eksekusi dan efisiensi memori pada benchmark terstandardisasi. Setiap instance direpresentasikan sebagai graf tak berarah berbobot dengan jarak Euclidean atau pseudo Euclidean sesuai spesifikasi TSPLIB, kemudian diproses oleh algoritma Prim, Kruskal, dan Borůvka dalam lingkungan pemrograman yang seragam, dengan pengukuran waktu eksekusi rata rata, variasi waktu, penggunaan memori rata rata, serta verifikasi bobot MST. Hasil menunjukkan bahwa pada pr264 dan att532 ketiga algoritma menghasilkan bobot MST yang identik dan optimal, sedangkan pada rat575 semuanya menghasilkan bobot sedikit di atas nilai referensi dengan deviasi yang sama, yang mengindikasikan adanya isu numerik pada perhitungan jarak. Dari sisi waktu, Kruskal secara konsisten menjadi algoritma tercepat pada semua dataset, dengan rata rata waktu sekitar satu orde magnitudo lebih kecil dibanding Prim dan Borůvka. Sebaliknya, Borůvka menunjukkan penggunaan memori yang paling hemat, dengan rata rata memori puluhan kali lebih kecil dibanding Prim, sementara Kruskal berada di posisi tengah. Temuan ini menegaskan bahwa, untuk graf lengkap berbasis TSPLIB, Kruskal merupakan pilihan utama untuk komputasi MST umum, Borůvka sesuai untuk skenario dengan keterbatasan memori atau potensi paralelisasi, dan Prim lebih tepat diposisikan sebagai baseline klasik untuk pembandingan teoretis dan eksperimen]]>
Copyrights © 2026
