De ce contează?
Imaginează-ți că ai o singură insulă locuită într-un arhipelag și vrei să conectezi toate satele cu poduri, cheltuind cât mai puțin. Nu construiești poduri la întâmplare prin tot arhipelagul: pornești de la insula ta și, la fiecare pas, ridici cel mai ieftin pod care atinge un sat NOU, încă neconectat. Insula conectată crește treptat, sat cu sat, până le-ai prins pe toate. Exact așa lucrează algoritmul lui Prim.
Intuiția
Un arbore parțial de cost minim (APM) leagă toate nodurile cu cost total minim, fără cicluri. Prim îl construiește crescând un singur arbore dintr-un nod de start. La orice moment ai o mulțime de noduri „în arbore” și restul „afară”. Întrebarea repetată e simplă: care e cea mai ieftină muchie care leagă arborele de un nod din afară? O alegi, adaugi acel nod, și frontiera se mărește. Repeți până ai prins toate nodurile.
De ce e corectă alegerea lacomă? E aceeași proprietate a tăieturii de la Kruskal, aplicată tăieturii arbore / restul nodurilor: dintre toate muchiile care traversează tăietura, cea mai ieftină aparține sigur unui APM. Orice APM care ar ocoli-o trebuie să traverseze tăietura pe altundeva, cu o muchie cel puțin la fel de scumpă — o poți înlocui fără să crești costul. Diferența de stil: Kruskal întreține o pădure de bucăți care se unesc, Prim crește un singur arbore care înghite nod după nod.