Evaluasi Algoritma Kruskal dan Prim dalam Optimalisasi Pembangunan Infrastruktur Jaringan Internet Di Daerah Terpencil

Abstract

Penelitian ini membandingkan kinerja algoritma Kruskal dan Prim dalam membangun Minimum Spanning Tree (MST) pada sebuah graf berbobot. Hasil menunjukkan bahwa kedua algoritma menghasilkan MST dengan bobot total yang sama, yaitu 7.0, meskipun menggunakan pendekatan yang berbeda. Algoritma Kruskal bekerja dengan memilih edge terkecil secara global, sedangkan algoritma Prim memulai dari satu node dan menambahkan edge dengan bobot terkecil yang terhubung. Dari segi efisiensi, algoritma Kruskal lebih cocok untuk graf jarang (sparse), sementara algoritma Prim lebih optimal untuk graf padat (dense). Kompleksitas algoritma Kruskal adalah O(E log E), sedangkan algoritma Prim bergantung pada representasi graf, dengan kompleksitas O(V²) atau O(E + V log V) menggunakan heap. Penelitian ini menyimpulkan bahwa pemilihan algoritma yang tepat bergantung pada karakteristik graf, di mana Kruskal ideal untuk jaringan dengan koneksi minim, sementara Prim lebih sesuai untuk jaringan dengan konektivitas tinggi, seperti pada pengembangan infrastruktur jaringan internet di daerah terpencil.