Una società deve collegare con la fibra otto edifici di un campus. Ogni possibile tratta ha un costo di scavo diverso. Non serve un collegamento diretto tra ogni coppia di edifici: basta che ognuno sia raggiungibile da tutti gli altri, eventualmente passando per edifici intermedi. Quali tratte conviene realizzare per spendere il meno possibile?
La risposta è un albero ricoprente minimo (in inglese MST, Minimum Spanning Tree). È uno dei rari problemi di ottimizzazione in cui un approccio avido, cioè scegliere a ogni passo l'opzione che sembra migliore, porta con certezza alla soluzione ottima.
Definizioni
Dato un grafo non orientato, connesso e pesato:
- un albero ricoprente è un sottoinsieme di archi che collega tutti i vertici senza formare cicli; con n vertici contiene esattamente n − 1 archi;
- un albero ricoprente minimo è quello con la somma dei pesi più bassa.
Se il grafo non è connesso si parla di foresta ricoprente minima, una per componente.
La proprietà del taglio
Tutti gli algoritmi per l'MST si basano su un'unica idea. Si divide l'insieme dei vertici in due parti qualsiasi; tra gli archi che attraversano la divisione, quello di peso minimo appartiene a un albero ricoprente minimo.
Il motivo: se un albero non contenesse quell'arco, aggiungendolo si formerebbe un ciclo che attraversa la divisione almeno un'altra volta, con un arco più pesante. Togliendo quest'ultimo si otterrebbe un albero di costo non superiore. Gli algoritmi di Kruskal e di Prim sono due modi diversi di applicare ripetutamente questa proprietà.
L'algoritmo di Kruskal
- Ordina tutti gli archi per peso crescente.
- Scorrili uno alla volta: aggiungi l'arco all'albero se collega due vertici che non sono ancora connessi; altrimenti scartalo, perché creerebbe un ciclo.
- Fermati quando hai n − 1 archi.
Il punto delicato è il passo 2: come sapere in fretta se due vertici sono già connessi? Si usa la struttura union-find (o insiemi disgiunti), che mantiene una partizione dei vertici e offre due operazioni: trovare il rappresentante dell'insieme di un vertice e fondere due insiemi.
def kruskal(n, archi):
padre = list(range(n))
def trova(x):
while padre[x] != x:
padre[x] = padre[padre[x]] # compressione del cammino
x = padre[x]
return x
albero, totale = [], 0
for w, u, v in sorted(archi):
ru, rv = trova(u), trova(v)
if ru != rv:
padre[ru] = rv
albero.append((u, v, w))
totale += w
return albero, totale
Con compressione dei cammini e unione per dimensione o rango le operazioni costano in pratica un tempo quasi costante. Il costo dominante diventa l'ordinamento: circa m log m.
L'algoritmo di Prim
Prim fa crescere un unico albero partendo da un vertice qualsiasi. A ogni passo aggiunge l'arco più leggero che collega un vertice già nell'albero a uno ancora fuori. La proprietà del taglio si applica alla divisione tra «dentro» e «fuori».
L'implementazione assomiglia molto a Dijkstra: una coda di priorità contiene i vertici esterni, con priorità uguale al peso del miglior arco che li collega all'albero, non alla distanza dalla sorgente. Con un heap binario il costo è circa (n + m) log n.
Quale scegliere
| Situazione | Scelta consigliata |
|---|---|
| Archi già in una lista, grafo sparso | Kruskal |
| Grafo denso o rappresentato con matrice | Prim con array, costo n² |
| Serve anche sapere quali gruppi si formano strada facendo | Kruskal |
| Archi generati al volo dai vicini | Prim |
In molti casi pratici le differenze sono piccole; Kruskal è più semplice da scrivere senza errori.
Un esempio
Quattro edifici A, B, C, D. Costi: A–B 3, A–C 1, B–C 7, B–D 5, C–D 4. Kruskal ordina: A–C (1), A–B (3), C–D (4), B–D (5), B–C (7). Prende A–C, poi A–B, poi C–D; a quel punto ha 3 archi e si ferma. Costo totale 8. B–D e B–C sono scartati perché chiuderebbero cicli.
Applicazioni concrete
- Progettazione di reti: cavi, tubazioni, linee elettriche, dove conta il costo complessivo di collegamento e non la distanza tra due punti specifici.
- Clustering: costruito l'MST su punti con pesi pari alle distanze, togliere i k − 1 archi più lunghi divide i dati in k gruppi ben separati. È il principio del clustering a legame singolo.
- Approssimazioni: l'MST fornisce un limite inferiore e una base di partenza per euristiche del commesso viaggiatore.
- Segmentazione di immagini: pixel come vertici e differenze di colore come pesi; i tagli sugli archi più pesanti separano le regioni.
Una precisazione importante: l'MST minimizza il costo totale, non le distanze. Nell'albero il percorso tra due edifici può essere molto più lungo del collegamento diretto. Se servono percorsi brevi tra coppie specifiche, il problema è un altro.
In sintesi
- L'albero ricoprente minimo collega tutti i vertici con n − 1 archi di costo totale minimo.
- La proprietà del taglio garantisce che le scelte avide siano corrette.
- Kruskal ordina gli archi e usa union-find per evitare i cicli, con costo circa m log m.
- Prim fa crescere un albero con una coda di priorità, in modo simile a Dijkstra.
- Oltre alle reti fisiche, l'MST serve per clustering, segmentazione e approssimazioni.
