Kompleksitas Waktu dan Ruang

Kompleksitas Waktu:

• Versi pemindaian edge di sini memiliki kompleksitas O(V * E): V-1 putaran, masing-masing memindai semua E edge. Dengan binary heap dan adjacency list, Prim berjalan dalam O((V + E) log V).

Kompleksitas Ruang:

• O(V) untuk array inTree (ditambah edge input).

Ringkasan:

• Prim menumbuhkan satu pohon dengan selalu menambahkan edge termurah yang keluar darinya, sampai semua vertex tercakup.
• Algoritma ini menghasilkan bobot total minimum yang sama seperti Kruskal, dengan strategi yang berbeda.