Algoritmo di Prim

Immagina di posare cavi a partire da una centrale elettrica: colleghi prima la città più vicina, poi la città più vicina a qualsiasi punto già collegato, e così via. Questo è l'algoritmo di Prim, e finisce sempre con la rete più economica possibile.

Un grafo con un albero che cresce da un nodo, i nodi in attesa intorno con i loro archi migliori tratteggiati, e sotto l'elenco dei nodi in attesa
Un grafo con un albero che cresce da un nodo, i nodi in attesa intorno con i loro archi migliori tratteggiati, e sotto l'elenco dei nodi in attesa

L'idea

Un albero ricoprente minimo collega tutti i nodi di un grafo pesato con la minima lunghezza totale degli archi. L'algoritmo di Prim lo costruisce facendo crescere un solo albero verso l'esterno da una partenza. L'albero non si divide mai in pezzi: a ogni passo entra esattamente un nuovo nodo, tramite l'arco più corto che esce dall'albero.

Passo per passo

Metti la partenza nell'albero. Per ogni nodo fuori dall'albero, tieni il suo arco migliore: il suo arco più corto verso un nodo qualsiasi dell'albero. Poi ripeti: scegli il nodo esterno con l'arco migliore più corto, aggiungilo all'albero con quell'arco ed esamina i suoi archi. Un vicino fuori dall'albero che ora si può raggiungere con un arco più corto prende quell'arco come nuovo migliore. Fermati quando tutti i nodi sono nell'albero.

Un esempio

Prendi gli archi A–B di lunghezza 1, B–C 2, A–C 3, C–D 4 e B–D 5, e parti da A. Gli archi di A danno a B l'arco migliore 1 e a C l'arco migliore 3. B è il più vicino, quindi entra con A–B; i suoi archi migliorano C a 2 e danno 5 a D. C entra con B–C, e il suo arco C–D migliora D a 4. Infine D entra con C–D. L'albero A–B, B–C, C–D ha lunghezza totale 1 + 2 + 4 = 7.

Perché è corretto

A ogni passo i nodi sono divisi in due gruppi: quelli nell'albero e quelli fuori. La proprietà del taglio dice che l'arco più corto tra due gruppi così appartiene sempre a qualche albero ricoprente minimo. Prim aggiunge sempre proprio quell'arco, quindi l'albero costruito finora si può sempre completare in un albero ricoprente minimo, e quando tutti i nodi sono entrati, lo è.

Storia e velocità

Il matematico ceco Vojtěch Jarník pubblicò l'algoritmo nel 1930. Robert Prim lo riscoprì ai Bell Labs nel 1957, ed Edsger Dijkstra di nuovo nel 1959. Con i nodi in attesa in un heap binario, il lavoro cresce come E log V per V nodi ed E archi; con un semplice array è circa V², il che è meglio quando quasi ogni coppia di nodi è collegata. Con un heap di Fibonacci è E + V log V.

Provalo

Apri l'app, fai clic su un nodo per partire da lì e premi Passo. I nodi nell'albero sono verdi, quelli in attesa blu, e l'arco migliore di ogni nodo in attesa è tratteggiato. I nodi in attesa sono elencati sotto il grafo con la lunghezza del loro arco migliore, dal più corto: il primo è il prossimo a entrare. Parti da nodi diversi e guarda l'ordine cambiare mentre il totale resta lo stesso.

Domande frequenti

Qual è la differenza tra l'algoritmo di Prim e quello di Dijkstra?

Entrambi fanno crescere una regione da una partenza usando una coda di priorità. Prim ordina un nodo in attesa in base alla lunghezza del suo arco migliore verso l'albero; Dijkstra in base alla sua intera distanza dalla partenza. Prim dà un albero ricoprente minimo, Dijkstra un albero dei percorsi più brevi.

L'algoritmo di Prim funziona con lunghezze negative degli archi?

Sì. A differenza dell'algoritmo di Dijkstra, Prim confronta solo archi tra loro, quindi le lunghezze negative non creano problemi: trova comunque un albero ricoprente con il totale minimo.

E se il grafo non è connesso?

Allora l'algoritmo di Prim si ferma quando ha raggiunto tutti i nodi che può raggiungere: dà un albero ricoprente minimo solo del pezzo che contiene la partenza. Rieseguirlo da un nodo non ancora raggiunto dà una foresta ricoprente minima.

È meglio l'algoritmo di Prim o quello di Kruskal?

Nessuno vince sempre. Prim è adatto ai grafi densi e ai grafi memorizzati come liste di vicini; Kruskal ai grafi sparsi dati come elenco di archi. Entrambi trovano un albero della stessa lunghezza totale.

Pronto a provarlo?

Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.

Prova l'algoritmo di Prim