Motivazione

Kruskal mantiene la foresta crescente di archi scelti in una struttura union-find. Per aggiungere un arco in sicurezza, controlla se i due estremi sono già nello stesso insieme (in tal caso si formerebbe un ciclo).

Perché imparare Kruskal?

• MST reali: progettazione di reti, clustering e posa di cavi o strade al costo minimo.
• Union-find: una struttura elegante e riutilizzabile per tenere traccia della connettività, che ricorre in molti ambiti dell'informatica.
• Correttezza greedy: un altro esempio in cui scegliere sempre l'opzione sicura più economica produce l'ottimo globale.

Tutti gli alberi ricoprenti minimi di un grafo usano lo stesso multinsieme di pesi degli archi, quindi il peso totale (e l'arco più grande) è unico.