Algoritmo di Kruskal

Considera ciascun arco in ordine non decrescente di peso

• caso 1: se $e$ crea un ciclo allora scarta $e$
• caso 2: altrimenti inserisce $e$ in $T$

Siccome gli archi selezionati dall’algoritmo non creano cicli in $T$ allora durante l’esecuzione dell’algoritmo, il grafo formato dai nodi di $V$ insieme agli archi di $T$ è una foreste di alberi, cioè le componenti connesse del grafo $(V,T)$ sono alberi

Correttezza dell’algoritmo di Kruskal

L’insieme di archi $T$ prodotto dall’algoritmo di Kruskal è un MST

Implementazione dell’algoritmo di Kruskal

• abbiamo bisogno di rappresentare le componenti connesse (alberi della foresta)
• ciascuna componente connessa è un insieme di vertici disgiunto da ogni altro insieme

Union-Find

• ciascun albero della foresta è rappresentato dal suo insieme di vertici
• per rappresentare questi insiemi di vertici si utilizza la struttura dati Union-Find per la rappresentazione di insiemi disgiunti

Operazioni supportate dalla struttura dati Union-Find:

• MakeUnionFind(S) crea una collezione di insiemi ognuno dei quali contiene un elemento di $S$
  • nella fase di inizializzazione dell’algoritmo di Kruskal viene invocato MakeUnionFind(V): ciascun insieme creato corrisponde ad un albero con un solo vertice
• Find(x) restituisce l’insieme che contiene $x$
  • per ciascun arco esaminato $(u,v)$ l’algoritmo di Kruskal invoca Find(u) e Find(v)
  • se entrambe le chiamate restituiscono lo stesso insieme allora vuol dire che $u$ e $v$ sono nello stesso albero e quindi $(u,v)$ crea un ciclo in $T$
• Union(X,Y) unisce gli insiemi $X$ e $Y$
  • se l’arco $(u,v)$ non crea un ciclo in $T$ allora l’algoritmo di Kruskal invoca Union(Find(u), Find(v)) per unire le componenti connesse di $u$ e $v$ in un’unica componente connessa

Implementazione dell’algoritmo di Kruskal con Union-Find