Motivazione

Mentre Kruskal ordina tutti gli archi globalmente e usa una struttura union-find, Prim mantiene un unico albero in crescita e cerca ripetutamente il vertice esterno più vicino.

Perché imparare Prim?

• Grafi densi: Prim, con le strutture dati giuste, è efficiente quando ci sono molti archi.
• Proprietà del taglio: è un esempio pratico del motivo per cui l’arco meno costoso che esce dall’albero corrente è sempre sicuro da aggiungere.
• Due prospettive sullo stesso problema: confrontare Prim e Kruskal approfondisce la comprensione degli alberi ricoprenti minimi.

Poiché tutti gli MST di un grafo condividono gli stessi pesi degli archi, Prim e Kruskal riportano sempre lo stesso peso totale.