Come funziona l’algoritmo di Prim

L’algoritmo di Prim è un metodo per trovare l’albero di copertura minimo (MST) di un grafo. In pratica, serve a trovare un insieme di archi che collegano tutti i nodi di un grafo senza cicli, e il loro peso totale è il più basso possibile. Robert C. Prim è un matematico e informatico statunitense, famoso per aver ideato l’algoritmo di Prim. Questo algoritmo è stato sviluppato nel 1957 mentre lavorava nel campo dei grafi e delle strutture di dati, ed è utilizzato per trovare l’albero di copertura minimo (MST) di un grafo. In pratica, l’albero di copertura minimo è un insieme di archi che collega tutti i nodi di un grafo con il minor peso totale possibile, senza formare cicli.

L’algoritmo di Prim è uno dei più noti metodi “greedy” (golosi) per risolvere questo problema, in cui si cerca sempre di fare la scelta più vantaggiosa a breve termine, per costruire una soluzione globale ottimale.

A che cosa serve?

L’algoritmo di Prim, sebbene sia un concetto matematico e computazionale, ha applicazioni pratiche in vari campi dove è necessario ottimizzare la connessione tra diversi punti, minimizzando il costo o il peso. Ecco alcune applicazioni nella vita reale:

1. Reti di telecomunicazioni: In un contesto di reti, come Internet o reti telefoniche, l’algoritmo di Prim può essere usato per costruire una rete di collegamenti tra diversi nodi (come computer o torri di telecomunicazione) con il minimo costo. In pratica, ti aiuta a connettere tutte le “stazioni” in modo che la connessione totale sia la più economica possibile.
2. Reti elettriche e infrastrutture: Può essere utilizzato per progettare la rete elettrica di una città o di una regione, dove gli “archi” sono le linee elettriche e i “nodi” sono le stazioni di distribuzione. L’algoritmo aiuta a connettere tutte le stazioni in modo che la spesa per le linee di trasmissione sia la più bassa possibile, minimizzando i costi di costruzione e mantenimento.
3. Pianificazione di rotte di trasporto: Immagina di dover pianificare un sistema di trasporti tra diverse città o hub. L’algoritmo di Prim può essere usato per determinare il modo più economico per connettere tutte le città, minimizzando i costi complessivi della costruzione delle infrastrutture (come strade, ferrovie, o reti di trasporto aereo).
4. Progettazione di circuiti elettrici: Quando si progettano circuiti elettronici complessi, l’algoritmo di Prim può aiutare a determinare il percorso ottimale per le connessioni tra vari componenti del circuito, minimizzando il cablaggio e riducendo i costi.
5. Gestione delle risorse naturali: Può essere utilizzato per gestire la distribuzione di risorse, come l’acqua o il gas, in modo che la rete di distribuzione sia la più economica possibile, riducendo gli sprechi e i costi di distribuzione.

In sostanza, l’algoritmo di Prim è utile in tutte le situazioni in cui è necessario “collegare” un insieme di elementi (nodi) con il minor “costo” possibile, come costruire una rete, una mappa di collegamenti o qualsiasi altro tipo di infrastruttura.

Come funziona l’algoritmo di Prim

Ecco come funziona, spiegato in modo semplice:

1. Inizia da un nodo a caso: Parti da uno qualsiasi dei nodi del grafo.
2. Trova l’arco più corto: Guarda tutti gli archi che partono dal nodo che hai appena scelto e scegli quello che ha il peso minore.
3. Aggiungi il nodo collegato: Aggiungi il nodo collegato dall’arco appena selezionato all’albero (cioè, ora questo nodo fa parte della soluzione).
4. Ripeti: Ora guarda tutti gli archi che partono da uno dei nodi che fanno parte dell’albero e ripeti il passaggio 2, fino a quando tutti i nodi sono stati aggiunti all’albero.

Un esempio

Immagina un grafo con 5 nodi: A, B, C, D, E. Gli archi e i loro pesi sono:

• A – B (peso 2)
• A – C (peso 3)
• B – D (peso 4)
• C – E (peso 5)
• D – E (peso 6)
• B – E (peso 7)
• C – D (peso 8)

1. Inizia da A: Il nodo A è scelto come punto di partenza.
2. Trova l’arco più corto da A: Guardiamo gli archi che partono da A. Sono A-B (peso 2) e A-C (peso 3). L’arco con il peso più basso è A-B.
3. Aggiungi B all’albero: Aggiungiamo il nodo B all’albero e l’arco A-B con peso 2.
4. Trova l’arco più corto che collega un nodo già nell’albero con un nodo fuori dall’albero: Ora guardiamo gli archi che collegano i nodi A e B (già nell’albero) con i nodi fuori dall’albero. Gli archi disponibili sono:
   • B-D (peso 4)
   • A-C (peso 3) L’arco con il peso più basso è A-C (peso 3).
5. Aggiungi C all’albero: Aggiungiamo il nodo C all’albero e l’arco A-C con peso 3.
6. Trova il prossimo arco più corto: Ora guardiamo gli archi che collegano A, B e C ai nodi rimanenti. Gli archi sono:
   • B-D (peso 4)
   • C-E (peso 5) Il più corto è B-D (peso 4).
7. Aggiungi D all’albero: Aggiungiamo D all’albero e l’arco B-D con peso 4.
8. Trova l’ultimo arco: Ora, l’unico arco che rimane è C-E (peso 5).
9. Aggiungi E all’albero: Aggiungiamo E all’albero e l’arco C-E con peso 5.

Alla fine, l’albero di copertura minimo è formato dagli archi A-B (peso 2), A-C (peso 3), B-D (peso 4) e C-E (peso 5), per un peso totale di 14.

In pratica, Prim cerca sempre il “colpo” più conveniente (l’arco con il peso minore) per espandere l’albero, fino a collegare tutti i nodi con il peso complessivo più basso possibile.

Come implementare l’algoritmo di Prim in Python

import heapq

def prim(graph, start):
# Inizializza i nodi visitati e l'albero di copertura minimo (MST)
visited = set() # Insieme di nodi visitati
mst = [] # Elenco degli archi nell'albero di copertura minimo
total_weight = 0 # Peso totale dell'MST

# Crea una coda di priorità (min-heap) per tenere traccia degli archi
min_heap = [(0, start)] # (peso, nodo) (iniziamo con peso 0 per il nodo di partenza)

while min_heap:
weight, node = heapq.heappop(min_heap) # Estrai l'arco con peso minimo

if node not in visited:
visited.add(node) # Aggiungi il nodo all'insieme dei nodi visitati
total_weight += weight # Aggiungi il peso dell'arco all'MST
if weight > 0: # Non aggiungere il nodo iniziale con peso 0
mst.append((prev_node, node, weight)) # Aggiungi l'arco all'MST

# Aggiungi i nodi adiacenti non visitati alla coda di priorità
for adj_node, adj_weight in graph[node]:
if adj_node not in visited:
heapq.heappush(min_heap, (adj_weight, adj_node))
prev_node = node # Memorizza il nodo da cui proviene l'arco

return mst, total_weight

# Esempio di grafo rappresentato come un dizionario di liste di adiacenza
graph = {
'A': [('B', 2), ('C', 3)],
'B': [('A', 2), ('D', 4), ('E', 7)],
'C': [('A', 3), ('E', 5), ('D', 8)],
'D': [('B', 4), ('C', 8), ('E', 6)],
'E': [('B', 7), ('C', 5), ('D', 6)],
}

# Esegui l'algoritmo di Prim a partire dal nodo 'A'
mst, total_weight = prim(graph, 'A')

print("Albero di copertura minimo (MST):", mst)
print("Peso totale dell'MST:", total_weight)