Questa voce o sezione sugli argomenti algoritmi e teoria dei grafi non cita le fonti necessarie o quelle presenti sono insufficienti.

---

Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti.

Algoritmo di Kruskal
Classe	Albero ricoprente minimo
Struttura dati	Grafo
Caso peggiore temporalmente	${\displaystyle O(|E|\log |V|)}$ (usando Mfset)
Caso peggiore spazialmente	${\displaystyle \Omega (|E|+|V|)}$
Manuale

L'algoritmo di Kruskal è un algoritmo goloso^[1] ottimo utilizzato per calcolare gli alberi di supporto minimi di un grafo non orientato.

Prende il nome dal matematico americano Joseph Kruskal che lo ideò e propose nel 1956.

Si consideri un grafo non orientato e connesso dove ${\displaystyle V}$ rappresenta il numero di vertici (o nodi) ed ${\displaystyle E}$ il numero di spigoli (o archi). Ad ogni spigolo è associato un peso (o distanza): lo scopo dell'algoritmo è quello di trovare un albero ricoprente di peso minimo, cioè quello in cui la somma dei pesi sia minima. L'algoritmo può essere applicato solo se si dispone di due o più vertici.

L'algoritmo di Kruskal si basa sulla seguente semplice idea: ordiniamo gli archi in ordine crescente di costo e successivamente li analizziamo singolarmente, inserendo l'arco nella soluzione se non forma cicli con gli archi precedentemente selezionati. Notiamo che ad ogni passo, se abbiamo più archi con lo stesso costo, è indifferente quale viene scelto.

Lo scopo di questi tipi di problemi è trovare un percorso minimo che copra tutti i nodi della rete indipendentemente dall'ordine. Bisogna schematizzare il problema come nella figura qui sotto indicando con delle lettere i nodi (ossia i punti della rete che dobbiamo collegare) e con dei segmenti i possibili collegamenti tra i nodi, ad ognuno dei quali deve essere assegnato un numero che può indicare un costo, una distanza o comunque un valore da minimizzare.

Un esempio pratico potrebbe essere il progetto di una rete locale di computer dove ogni PC deve essere collegato alla rete ma utilizzando il minor numero possibile di cavi per il collegamento.

Impostiamo quindi un grafo in cui indichiamo con le lettere maiuscole dell'alfabeto i computer (nodi) e con dei segmenti (che si chiamano archi) a cui è associata una certa distanza, ossia la lunghezza di cavo necessaria per collegarli.

In questo caso si sta considerando una rete composta da quattro nodi ${\displaystyle \{A,B,C,D\}}$ e 6 archi che rappresentano i possibili collegamenti. Prima di proseguire vanno precisate due cose: l'arco ${\displaystyle AD}$ e l'arco ${\displaystyle BC}$ non si toccano e, in generale, non è necessario che ogni nodo sia collegato a tutti gli altri.

Per trovare l'albero ricoprente (a peso) minimo si procede elencando tutti gli archi in ordine crescente di costo (in questo caso distanza). Si ottiene quindi il seguente elenco:

• ${\displaystyle AB}$ 1
• ${\displaystyle BC}$ 2
• ${\displaystyle AC}$ 3
• ${\displaystyle BD}$ 3
• ${\displaystyle CD}$ 4
• ${\displaystyle AD}$ 5

Nel caso ci fossero due archi (in questo caso ${\displaystyle BD}$ e ${\displaystyle AC}$) con uno stesso costo si possono indicare in un ordine a piacere lasciando inalterato il risultato. Convenzionalmente si usa disporli in ordine alfabetico.

Ora, per trovare il minimo albero coprente dobbiamo considerare nuovamente il grafico iniziale andando ad evidenziare gli archi, procedendo nell'ordine dell'elenco appena descritto, in modo da non creare circoli chiusi. Vediamo in pratica come si procede: evidenziamo l'arco ${\displaystyle AB}$ (costo 1) e lo segnaliamo nell'elenco:

Elenco degli archi ${\displaystyle \mathbf {AB} }$ 1 ${\displaystyle BC}$ 2 ${\displaystyle AC}$ 3 ${\displaystyle BD}$ 3 ${\displaystyle CD}$ 4 ${\displaystyle AD}$ 5

Procediamo considerando l'arco ${\displaystyle BC}$ (costo 2) e, analogamente a quanto appena fatto, lo evidenziamo nel grafico e lo segniamo nell'elenco:

Elenco degli archi ${\displaystyle \mathbf {AB} }$ 1 ${\displaystyle \mathbf {BC} }$ 2 ${\displaystyle AC}$ 3 ${\displaystyle BD}$ 3 ${\displaystyle CD}$ 4 ${\displaystyle AD}$ 5

Il prossimo arco dell'elenco sarebbe ${\displaystyle AC}$ (costo 3) ma lo saltiamo perché creerebbe un circolo chiuso in quanto collegherebbe insieme il nodo ${\displaystyle A}$ e il nodo ${\displaystyle C}$ che sono già collegati attraverso ${\displaystyle B}$ e lo scopo del problema è creare una rete in cui tutti i nodi sono collegati ma utilizzando il minor cavo possibile.

Si procede dunque con ${\displaystyle BD}$ (costo 3) colorando l'arco di rosso ed evidenziandolo nell'elenco:

Elenco degli archi ${\displaystyle \mathbf {AB} }$ 1 ${\displaystyle \mathbf {BC} }$ 2 ${\displaystyle AC}$ 3 ${\displaystyle \mathbf {BD} }$ 3 ${\displaystyle CD}$ 4 ${\displaystyle AD}$ 5

Ora tutti i nodi sono collegati alla rete quindi il problema è concluso. Procedendo con l'elenco, infatti, si potrebbe verificare che gli altri archi rimanenti creerebbero solamente circoli chiusi.

Per concludere si può facilmente calcolare il costo totale della rete facendo la somma dei costi degli archi segnati (quelli che sono stati evidenziati durante l'esercizio). Il costo totale della rete è

${\displaystyle AB+BC+BD=1+2+3=6.}$

Se avessimo espresso i costi (ossia le distanze) tra i nodi in metri (per esempio per collegare il nodo ${\displaystyle A}$ al nodo ${\displaystyle B}$ serve 1 metro di cavo di rete) avremmo ottenuto che per realizzare la rete (al minor costo riguardante il cavo) servirebbero 6 metri di cavo.

L'idea di base di Kruskal è la seguente: gestire una foresta di alberi disgiunti tra loro in modo tale da selezionare solo gli archi, di peso minimo, che collegano tra loro questi alberi. Tutti gli alberi della foresta devono essere aciclici.

L'algoritmo gestisce una foresta di alberi, ognuno dei quali durante tutta l'esecuzione rimane aciclico. La foresta durante tutta l'esecuzione è sottoinsieme di qualche MST del grafo che si sta considerando. Quando inizia l'algoritmo la foresta è formata dai soli vertici del grafo, senza archi definiti.

Formalmente

Consideriamo ${\displaystyle G=(V,E)}$ il grafo connesso, non orientato e pesato. Consideriamo ${\displaystyle X}$ sottoinsieme degli archi ${\displaystyle E.}$ Inizialmente ${\displaystyle X}$ è vuoto ed è sottoinsieme di qualche MST. Consideriamo ${\displaystyle G_{X}=(V,X)}$ contenente tutti i vertici di ${\displaystyle G.}$ Inizialmente il grafo ${\displaystyle G_{X}}$ non contiene archi. La foresta quindi è formata da ${\displaystyle |V|}$ alberi disgiunti, dove ${\displaystyle |V|}$ è il numero di nodi.

Durante l'esecuzione l'algoritmo ricerca un arco sicuro da aggiungere alla foresta. Ricerca, fra tutti gli archi che collegano due alberi qualsiasi nella foresta, un arco ${\displaystyle (u,v)}$ di peso minimo.

Quindi esiste una invariante di ciclo.

Finché ${\displaystyle G_{X}}$ non sarà composta da un solo albero, ogni albero contenuto in ${\displaystyle G_{X}}$ sarà aciclico e ${\displaystyle G_{X}}$ sarà un sottoinsieme di qualche MST.

Una possibile implementazione dell'algoritmo di Kruskal potrebbe essere la seguente:

• Creare la foresta di grafi.
• Ordinare tutti gli archi del grafo in ordine crescente.
• Scandire gli archi ordinati, uno per volta, inserendoli se opportuno nella foresta.
• L'arco per essere aggiunto alla foresta deve collegare due alberi disgiunti.
• L'arco deve essere sicuro.
• L'arco non deve generare cicli, sempre vero se l'arco unisce due alberi disgiunti.

L'implementazione che viene descritta utilizza il TDA Partition e il TDA PriorityQueue. Il TDA Partition viene utilizzato per mantenere un insieme di oggetti disgiunti (insiemi disgiunti). Il TDA PriorityQueue invece viene utilizzato per mantenere la lista degli archi ordinati dal più piccolo al più grande.

Consideriamo ${\displaystyle G=(V,E)}$ il grafo connesso, non orientato e pesato. Consideriamo ${\displaystyle X}$ sottoinsieme di ${\displaystyle E.}$ Quindi ${\displaystyle G_{X}=(V,X)}$ conterrà la foresta.

Q sarà la PriorityQueue
P sarà la Partizione

${\displaystyle X=\varnothing }$
per ogni v vertice di V[G]
P.MAKE-SET(v) // all'interno della partizione vengono inseriti i vari alberi disgiunti
per ogni (u,v) arco di E[G]
Q.ADD(P,(u,v)) // gli archi vengono ordinati dal più piccolo al più grande

// La foresta è ora memorizzata nella partizione e tutti gli archi in ordine crescente nella coda a priorità.

finché la coda Q non è vuota
(u,v) = EXTRACT-MIN(Q)
if P.FIND-SET(u) != FIND-SET(v)
X = X UNION {(u,v)}
P.UNION(u,v)

La partizione viene utilizzata per capire se due vertici fanno parte dello stesso albero, quindi per mantenere valida l'invariante di ciclo. Analizziamo due casi che potrebbero verificarsi durante l'esecuzione del ciclo finché:

• Se l'arco ${\displaystyle (u,v)}$ estratto dalla coda Q ha insiemi SET disgiunti vuol dire che è sicuro per ${\displaystyle X}$ infatti l'arco unirebbe due alberi distinti nella foresta. L'arco ${\displaystyle (u,v)}$ viene quindi aggiunto all'insieme ${\displaystyle X}$ in modo tale che ${\displaystyle X}$ mantenga l'invariante di ciclo. I due SET vengono poi uniti insieme in modo da identificare un solo albero.
• Se l'arco ${\displaystyle (u,v)}$ estratto da Q collega due vertici che fanno già parte dello stesso albero significa che l'arco non è sicuro per ${\displaystyle X.}$ Infatti se venisse aggiunto a ${\displaystyle X}$ si verrebbe a creare un ciclo in ${\displaystyle X.}$ L'arco viene quindi scartato.

NB: vi è un abuso di notazione dopo i commenti sotto l'istruzione q.add(p....)

Il costo computazionale dell'algoritmo è nel caso peggiore ${\displaystyle O(|V|\cdot |E|)}$ dove ${\displaystyle |E|}$ è il numero di archi e ${\displaystyle |V|}$ il numero di vertici. È possibile diminuire il costo computazionale dell'algoritmo sino ad ottenere ${\displaystyle O(|E|\log |V|)}$ solo utilizzando strutture union-find. Si può migliorare ulteriormente la complessità temporale usando la compressione di cammino del quick-union, che riduce il singolo costo della find a ${\displaystyle O(\log ^{*}n)}$, ottenendo una complessità temporale di ${\displaystyle O(|E|\log ^{*}|V|)}$

• Robert E. Tarjan, Data structures and network algorithms, Philadelphia, Society for Industrial and Applied Mathematics, 1983, ISBN 978-0-89871-187-5, OCLC 10120539.

• Algoritmo di Prim
• Algoritmo di Dijkstra
• Algoritmo di Floyd-Warshall

• Wikimedia Commons contiene immagini o altri file sull'algoritmo di Kruskal

Portale Informatica

Portale Matematica