algoritmo di Kruskal

L'algoritmo di Kruskal è un algoritmo ottimo utilizzato per calcolare gli alberi di supporto minimi di un grafo non orientato e con gli archi con costi non negativi. 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.