Motivasi

Kruskal mengurutkan semua sisi secara global dan menggunakan union-find, sedangkan Prim mempertahankan satu pohon yang terus berkembang dan berulang kali menjangkau simpul terdekat di luar pohon.

Mengapa mempelajari Prim?

• Graf padat: Prim dengan struktur yang tepat efisien saat ada banyak sisi.
• Sifat cut: algoritma ini menunjukkan secara langsung mengapa sisi termurah yang keluar dari pohon saat ini selalu aman untuk ditambahkan.
• Dua sudut pandang untuk satu masalah: membandingkan Prim dan Kruskal memperdalam pemahamanmu tentang pohon merentang minimum.

Karena semua MST pada sebuah graf memiliki bobot sisi yang sama, Prim dan Kruskal selalu menghasilkan total bobot yang sama.