Algoritmo di Kruskal

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

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

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

Si consideri un grafo non orientato e connesso dove $V$ rappresenta il numero di vertici (o nodi) ed $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.

Esempio dell'algoritmo di Kruskal su un grafo connesso, con i pesi basati sulla distanza euclidea

Esempio pratico risolto

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 $\{A,B,C,D\}$ e 6 archi che rappresentano i possibili collegamenti. Prima di proseguire vanno precisate due cose: l'arco $AD$ e l'arco $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:

• $AB$ 1
• $BC$ 2
• $AC$ 3
• $BD$ 3
• $CD$ 4
• $AD$ 5

Nel caso ci fossero due archi (in questo caso $BD$ e $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 $AB$ (costo 1) e lo segnaliamo nell'elenco:

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

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

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

Il prossimo arco dell'elenco sarebbe $AC$ (costo 3) ma lo saltiamo perché creerebbe un circolo chiuso in quanto collegherebbe insieme il nodo $A$ e il nodo $C$ che sono già collegati attraverso $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 $BD$ (costo 3) colorando l'arco di rosso ed evidenziandolo nell'elenco:

Elenco degli archi $\mathbf {AB}$ 1 $\mathbf {BC}$ 2 $AC$ 3 $\mathbf {BD}$ 3 $CD$ 4 $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 è

$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 $A$ al nodo $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'algoritmo

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.

Proprietà dell'algoritmo

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 $G=(V,E)$ il grafo connesso, non orientato e pesato. Consideriamo $X$ sottoinsieme degli archi $E.$ Inizialmente $X$ è vuoto ed è sottoinsieme di qualche MST. Consideriamo $G_{X}=(V,X)$ contenente tutti i vertici di $G.$ Inizialmente il grafo $G_{X}$ non contiene archi. La foresta quindi è formata da $|V|$ alberi disgiunti, dove $|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 $(u,v)$ di peso minimo.

Quindi esiste una invariante di ciclo.

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

Implementazione dell'algoritmo

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 $G=(V,E)$ il grafo connesso, non orientato e pesato. Consideriamo $X$ sottoinsieme di $E.$ Quindi $G_{X}=(V,X)$ conterrà la foresta.

Q sarà la PriorityQueue
P sarà la Partizione

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

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

Complessità computazionale dell'algoritmo

Il costo computazionale dell'algoritmo è nel caso peggiore $O(|V|\cdot |E|)$ dove $|E|$ è il numero di archi e $|V|$ il numero di vertici. È possibile diminuire il costo computazionale dell'algoritmo sino ad ottenere $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 $O(\log ^{*}n)$, ottenendo una complessità temporale di $O(|E|\log ^{*}|V|)$

Bibliografia

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

Voci correlate

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

Altri progetti

Altri progetti

• Wikimedia Commons

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