Algoritmo di Kruskal: Come Trovare il Minimum Spanning Tree (con Esempio in Python)

Cos'è e come funziona l'algoritmo di Kruskal

Immagina di avere un budget limitato e l’incarico di cablare un’intera regione montuosa con la fibra ottica.

Hai la mappa dei villaggi e sai esattamente quanto costa scavare tra un paese e l’altro.

Il tuo obiettivo è semplice, ma spietato: tutti i villaggi devono essere connessi alla rete, ma devi spendere il minor numero di euro possibile. Non puoi andare a tentativi, ti serve un metodo matematicamente infallibile.

È esattamente per scenari come questo che è nato l’algoritmo di Kruskal.

Ideato nel 1956, questo algoritmo è uno strumento potentissimo per trovare quello che in informatica chiamiamo Minimum Spanning Tree (MST), ovvero l’albero di connessione di costo minimo.

In questa guida vedremo in modo molto pratico come ragiona, perché funziona e come puoi implementarlo in Python per risolvere problemi di ottimizzazione reali.

Algoritmo di Kruskal: Spiegazione Facile

A cosa serve?

L’algoritmo di Kruskal serve a risolvere un problema classico sui grafi: trovare il Minimum Spanning Tree (MST), cioè l’albero di connessione di costo minimo. In parole semplici: dato un insieme di nodi (città, computer, ecc.) e possibili collegamenti tra loro, ciascuno con un costo (distanza, tempo, denaro), vogliamo selezionare un sottoinsieme di collegamenti che:

Connetta tutti i nodi (direttamente o indirettamente).
Non formi cicli (quindi sia un albero).
Abbia il costo totale più basso possibile.

È un problema fondamentale nelle reti (elettriche, informatiche, di trasporto) e nella progettazione di circuiti.

L’idea intuitiva

Immagina di dover collegare tutte le città di una regione con una rete ferroviaria, minimizzando i costi di costruzione. Una strategia semplice ed efficace è: prendi il collegamento più economico disponibile, purché non crei un ciclo (cioè non colleghi due città già collegate indirettamente). Poi ripeti finché tutte le città non sono raggiungibili.

Questa è esattamente l’idea di Kruskal: un algoritmo greedy che a ogni passo sceglie l’arco di peso minore tra quelli rimasti, ma lo aggiunge alla soluzione solo se non forma un ciclo con gli archi già scelti.

Come funziona

Ordina tutti gli archi per peso crescente.
Inizializza una struttura che tenga traccia di quali nodi sono già connessi tra loro (in pratica, crea un insieme per ogni nodo).
Scorri gli archi in ordine crescente:
- Per ogni arco [math](u, v)[/math] con peso [math]w[/math]:
- Se [math]u[/math] e [math]v[/math] appartengono a insiemi diversi (cioè non sono ancora collegati), allora:
  - Aggiungi l’arco all’MST.
  - Unisci i due insiemi (ora [math]u[/math] e [math]v[/math] fanno parte della stessa componente connessa).
- Altrimenti, salta l’arco (creerebbe un ciclo).
Fermati quando hai aggiunto esattamente [math]N-1[/math] archi (dove [math]N[/math] è il numero di nodi), perché un albero con [math]N[/math] nodi ha sempre [math]N-1[/math] archi.

La struttura Union-Find

Per gestire gli insiemi in modo efficiente, Kruskal usa una struttura dati chiamata Union-Find (o disjoint-set). Ha due operazioni principali:

Find(x): restituisce il rappresentante dell’insieme che contiene [math]x[/math].
Union(x, y): unisce i due insiemi che contengono [math]x[/math] e [math]y[/math].

Implementata con alberi e compressione dei cammini, queste operazioni sono quasi costanti (inverso della funzione di Ackermann). Questo rende l’algoritmo molto veloce.

Perché funziona? (Proprietà del taglio)

L’algoritmo di Kruskal è corretto grazie a una proprietà fondamentale dei grafi: la proprietà del taglio (cut property). In ogni taglio (partizione dei nodi in due sottoinsiemi), l’arco di peso minimo che attraversa il taglio appartiene a qualche MST.

Kruskal, aggiungendo sempre l’arco più leggero che non forma ciclo, sta implicitamente considerando tagli tra le componenti connesse già formate e il resto del grafo. L’arco scelto è il più leggero attraverso quel taglio, quindi può essere incluso in un MST. Questa scelta greedy porta alla soluzione ottima globale.

Forse potrebbe interessarti anche: Modello SLOBs nel Pharma: Guida Pratica Excel e Power Query per Gestire le Scadenze

Esempio

Consideriamo il grafo con 4 nodi (A, B, C, D) e archi:

[math]AB = 5, AC = 3, AD = 4, BC = 2, BD = 6, CD = 1[/math]

Passo 1: Ordina gli archi per peso:
[math]CD(1), BC(2), AC(3), AD(4), AB(5), BD(6)[/math]

Passo 2: Inizialmente ogni nodo è un insieme separato: [math]\{A\}, \{B\}, \{C\}, \{D\}[/math]

Elaborazione degli Archi (Passo 3)

In questa fase, l’algoritmo di Kruskal esamina gli archi uno alla volta, seguendo l’ordine di peso crescente stabilito nel Passo 1. L’obiettivo è connettere i nodi evitando la formazione di cicli.

1. Analisi dell’arco CD (Peso: 1)

Stato Insiemi: [math]C[/math] appartiene a [math]\{C\}[/math], [math]D[/math] appartiene a [math]\{D\}[/math].
Decisione: Poiché i nodi sono in insiemi diversi, non c’è rischio di ciclo.
Azione: Uniamo gli insiemi [math]\{C\}[/math] e [math]\{D\}[/math] in [math]\{C, D\}[/math] e aggiungiamo l’arco.
MST attuale: [math]\{CD\}[/math]

2. Analisi dell’arco BC (Peso: 2)

Stato Insiemi: [math]B[/math] appartiene a [math]\{B\}[/math], [math]C[/math] appartiene all’insieme già unito [math]\{C, D\}[/math].
Decisione: I nodi appartengono a componenti diverse.
Azione: Uniamo [math]\{B\}[/math] con [math]\{C, D\}[/math], creando l’insieme [math]\{B, C, D\}[/math].
MST attuale: [math]\{CD, BC\}[/math]

3. Analisi dell’arco AC (Peso: 3)

Stato Insiemi: [math]A[/math] appartiene a [math]\{A\}[/math], [math]C[/math] appartiene all’insieme [math]\{B, C, D\}[/math].
Decisione: I nodi sono ancora in insiemi separati.
Azione: Uniamo [math]\{A\}[/math] con [math]\{B, C, D\}[/math], ottenendo l’insieme finale [math]\{A, B, C, D\}[/math].
MST attuale: [math]\{CD, BC, AC\}[/math]

Conclusione dell’Algoritmo:

Abbiamo aggiunto esattamente [math]N – 1 = 3[/math] archi. Tutti i nodi sono ora parte dello stesso insieme (sono tutti connessi). L’algoritmo termina qui, ignorando gli archi rimanenti ([math]AD[/math], [math]AB[/math], [math]BD[/math]) che creerebbero inevitabilmente dei cicli.

Costo totale dell’MST:

[math]\displaystyle \text{Costo} = 1 + 2 + 3 = 6[/math]

Il grafico mostra a sinistra il grafo completo con tutti i 6 archi, a destra l’albero con i soli archi CD (1), BC (2) e AC (3).

Complessità

L’efficienza dell’algoritmo dipende principalmente da due fattori:

Ordinamento degli archi: [math]O(E \log E)[/math], dove [math]E[/math] è il numero di archi.
Ogni operazione Find/Union costa quasi [math]O(1)[/math] (inverso di Ackermann).

Totale: [math]O(E \log E)[/math], dominato dall’ordinamento.

Differenza con l’algoritmo di Prim

Un altro algoritmo famoso per l’MST è l’algoritmo di Prim, che parte da un nodo e via via aggiunge l’arco più leggero che collega un nodo già nell’albero a uno esterno. Mentre Kruskal lavora sugli archi in ordine globale, Prim lavora per espansione di un albero. Entrambi sono greedy e producono l’MST.

Ecco la sezione finale di confronto tra gli algoritmi di Kruskal e Prim, formattata in HTML responsive e ottimizzata per WordPress con la sintassi WP QuickLaTeX.

Quando usare Kruskal vs Prim?

Dato che sia Kruskal che Prim risolvono lo stesso problema (trovare il Minimum Spanning Tree), è lecito chiedersi quale scegliere. La risposta non è univoca: dipende dalla topologia della tua rete, in particolare dalla sua densità (il rapporto tra il numero di collegamenti e il numero di nodi).

In sintesi: Kruskal guarda la mappa globale e sceglie il collegamento più economico ovunque si trovi. Prim parte da una singola città e si allarga a macchia d’olio.

Caratteristica	Algoritmo di Kruskal	Algoritmo di Prim
Logica di base	Costruisce l’albero unendo gli archi più leggeri (approccio basato sugli archi).	Fa crescere un unico albero partendo da un nodo radice (approccio basato sui nodi).
Grafo ideale	Grafi sparsi (molti nodi, pochi archi).	Grafi densi (molti archi tra i nodi).
Struttura dati chiave	Union-Find (Disjoint-Set).	Coda di priorità (Min-Heap).
Complessità tipica	[math]O(E \log E)[/math] dove [math]E[/math] è il numero di archi.	[math]O(E + V \log V)[/math] usando un Fibonacci Heap.
Grafi disconnessi	Trova automaticamente una “foresta” (un MST per ogni sottorete isolata).	Richiede di essere riavviato per ogni componente disconnessa.

Forse potrebbe interessarti anche: Allocazione Budget con Python e MILP: Modelli, Codice e Soluzioni Pratiche

💡 Osservazione importante: L’algoritmo di Kruskal non richiede che il grafo sia connesso: se il grafo è disconnesso, troverà una foresta di copertura minima (minimum spanning forest), cioè un MST per ogni componente connessa.

Perché è vietato creare cicli?

Se aggiungessimo un arco che forma un ciclo, creeremmo un percorso ridondante: staremmo spendendo risorse per collegare due nodi che in realtà possono già comunicare tra loro attraverso un’altra strada. Rimuovendo l’arco più costoso di quel ciclo, manterremmo tutti i nodi connessi ma con un costo totale inferiore. Ecco perché un albero di connessione perfetto non ammette mai cicli.

Esercizio – Collegamento di villaggi con cavi (Difficile)

Testo
Devi portare la fibra ottica in tutti i villaggi di una regione montuosa. Hai a disposizione una mappa con le distanze (in km) tra coppie di villaggi. Vuoi collegare tutti i villaggi con una rete, posando cavi, minimizzando la lunghezza totale del cavo. Puoi scegliere quali collegamenti realizzare, purché alla fine ogni villaggio sia raggiungibile (direttamente o indirettamente) da ogni altro. Scrivi un algoritmo che trovi l’albero di connessione di costo minimo (Minimum Spanning Tree) usando l’algoritmo di Kruskal.

Esempio
Villaggi: A, B, C, D
Distanze: AB=5, AC=3, AD=4, BC=2, BD=6, CD=1
MST: CD(1), BC(2), AC(3) oppure CD(1), AD(4), AC(3) ma il minimo è CD+BC+AC=6.

Soluzione

Teoria: L’algoritmo di Kruskal è greedy: ordina gli archi per peso crescente e li aggiunge se non creano cicli. Per verificare i cicli si usa una struttura Union-Find (disjoint sets).

Implementazione:

Crea una lista di archi (u, v, peso).

Ordina per peso.

Inizializza un Union-Find con tutti i nodi.

Per ogni arco in ordine, se i due estremi non sono già connessi, uniscili e aggiungi l’arco alla soluzione.

Codice:

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    
def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False
        
        # Correzione formattazione indentazione
        if self.rank[rx] < self.rank[ry]: 
            self.parent[rx] = ry 
        elif self.rank[rx] > self.rank[ry]:
            self.parent[ry] = rx
        else:
            self.parent[ry] = rx
            self.rank[rx] += 1
        return True

  
def kruskal(nodi, archi):
    # archi: lista di (u, v, peso) con u e v interi (indici dei nodi)
    archi_ordinati = sorted(archi, key=lambda x: x[2])
    uf = UnionFind(len(nodi))
    mst = []
    costo_totale = 0
    
    for u, v, peso in archi_ordinati:
        if uf.union(u, v):
            mst.append((u, v, peso))
            costo_totale += peso
            if len(mst) == len(nodi) - 1:
                break
    return mst, costo_totale

# Test
nodi = ['A', 'B', 'C', 'D']
# Mappiamo i nomi a indici: A=0, B=1, C=2, D=3
archi = [(0,1,5), (0,2,3), (0,3,4), (1,2,2), (1,3,6), (2,3,1)]
mst, costo = kruskal(nodi, archi)
print("Albero di connessione:", mst)
print("Costo totale:", costo)

Albero di connessione: [(2, 3, 1), (1, 2, 2), (0, 2, 3)]
Costo totale: 6

💡 Osservazione
L’algoritmo di Kruskal costruisce un albero di copertura minimo aggiungendo sempre l’arco più leggero che non forma ciclo. La struttura Union-Find permette di verificare l’assenza di cicli in tempo quasi costante.

Forse potrebbe interessarti anche: Meteo e fatturato di un ristorante: come analizzare l’effetto del tempo con Python

Domanda di riflessione
Perché l’algoritmo di Kruskal è considerato greedy? Qual è la scelta locale che compie a ogni passo?

Risposta:

Kruskal è greedy perché a ogni passo sceglie l’arco di peso minimo tra quelli che non creano ciclo, basandosi solo sulla situazione corrente (gli archi già presi). Questa scelta locale porta all’albero di copertura minimo globale grazie alla proprietà di taglio (cut property) dei grafi: l’arco più leggero attraverso un taglio appartiene a qualche MST.

Commento Applicativo:

Dal punto di vista pratico, l’esercizio della fibra ottica dimostra la vera potenza dell’astrazione informatica. Abbiamo preso un problema fisico e logistico (cavi, montagne, chilometri) e lo abbiamo ridotto a un puro modello matematico.

La peculiarità di questo specifico caso d’uso sta nel fatto che l’algoritmo prende decisioni in modo estremamente miope (greedy): guarda solo il cavo più corto disponibile in quel preciso istante.

Nel mondo reale, prendere sempre la decisione che sembra più conveniente sul momento raramente porta al miglior risultato a lungo termine. Eppure, grazie alla struttura dei grafi e alla Cut Property, Kruskal ci dimostra matematicamente che, in questo specifico ambito aziendale/logistico, un approccio puramente “avido” e step-by-step garantisce in modo assoluto la soluzione globale perfetta.

Niente sprechi, nessuna ridondanza.

⚠️ Box: Errori comuni di implementazione

Quando si passa dalla teoria al codice, è facile inciampare in alcune trappole che compromettono l’efficienza o il funzionamento di Kruskal. Ecco gli errori più frequenti da evitare:

1. Dimenticare di ordinare gli archi

Sembra banale, ma è l’errore logico numero uno. Kruskal è un algoritmo greedy: se non ordini preventivamente l’intera lista degli archi dal più economico al più costoso, la proprietà fondamentale su cui si basa salta completamente e non otterrai il costo minimo.

2. Cercare i cicli con DFS o BFS

Per capire se l’aggiunta di un arco crea un ciclo, i programmatori alle prime armi spesso lanciano una ricerca in profondità (DFS) o in ampiezza (BFS) sul grafo in costruzione. Questo funziona, ma distrugge le prestazioni. Utilizzare la struttura dati Union-Find è un requisito obbligatorio per mantenere l’algoritmo veloce.

3. Non fermare il ciclo al momento giusto

Ricorda la regola d’oro: un albero che collega [math]N[/math] nodi ha esattamente [math]N-1[/math] archi. Una volta che hai inserito il numero corretto di archi nel tuo MST, devi interrompere l’esecuzione (break). Continuare a scorrere i restanti archi della lista ordinata è un inutile spreco di cicli di CPU.