Come funziona?

Union-find mantiene un array parent. Ogni vertice inizia come radice di sé stesso. Due operazioni guidano tutto:

• find(x): segui i collegamenti parent finché non raggiungi una radice (un vertice che è il proprio genitore). Due vertici sono connessi quando condividono una radice.
• union(a, b): collega una radice all’altra, unendo i due insiemi.

Algoritmo di Kruskal:

1. Elabora gli archi dal peso minore al maggiore.
2. Per ogni arco, trova le radici dei suoi estremi con find. Se sono diverse, l’arco unisce due componenti separate: uniscile con union e aggiungi il suo peso al totale.
3. Se le radici sono uguali, l’arco formerebbe un ciclo, quindi saltalo.

Dopo aver elaborato tutti gli archi, gli archi scelti formano l’MST (per un grafo connesso, esattamente n - 1 archi).