Algoritma Prim

            Adalah sebuah algoritma dalam teori graf untuk mencari pohon rentang minimum untuk sebuah graf berbobot yang saling terhubung. Algoritma prim ditemukan oleh seorang matematikawan bernama Vojtech Jarnik pada tahun 1930 dan kemudian secara terpisah oleh Computer Scientist Robert C. Prim pada tahun 1957 dan ditemukan kembali oleh Dijkstra pada 1959. Karena itu algoritma ini dinamai dengan Algoritma DJP atau Jarnik.

Langkah-langkahnya yaitu:

• membuat sebuh pohon yang terdiri dari satu nodem dipilih secara acak dari graf
• membuat sebuah himpunan yang berisi semua cabang di graf
• loop/ulang samapai semua cabang di dalam himpunan menghubungkan dua node di pohon
• hapus dari himpunan sau caabang dengan bobot terkecil yang menghubungkan satu node dengan satu node di luar pohon
• hubungkan cabang tersebut ke pohon

         Algortma prim dapat ditunjukkan berjalan dalam waktu O(Elog V), dimana E adalah jumlah cabang dan V adalah jumlah node, hal ini berdasarkan struktur data binary heap sederhana.

Sedangkan berdasarkan Fibonacci heap, hal ini dapat ditekan menjadi O(E + Vlog V), yang jauh lebih cepat bila grafiknya cukup padat sehingga E adalah Ω (Vlog V),