How it works?

Union-find conserve un tableau parent. Chaque sommet commence comme sa propre racine. Deux opérations pilotent l'ensemble :

• find(x) : suit les liens parent jusqu'à atteindre une racine (un sommet qui est son propre parent). Deux sommets sont connectés lorsqu'ils partagent une racine.
• union(a, b) : pointe une racine vers l'autre, fusionnant ainsi les deux ensembles.

Algorithme de Kruskal :

1. Traiter les arêtes du plus petit poids au plus grand.
2. Pour chaque arête, utiliser find pour trouver les racines de ses extrémités. Si elles diffèrent, l'arête relie deux parties distinctes : effectuez une opération union sur elles et ajoutez son poids au total.
3. Si les racines sont les mêmes, l'arête formerait un cycle, il faut donc l'ignorer.

Après avoir traité chaque arête, les arêtes choisies forment l'arbre couvrant minimal (pour un graphe connexe, il y en a exactement n - 1).