51. Algorithme de Kruskal : Utilisation de la structure Disjoint Set Union (DSU)

Kruskal's est un autre algorithme glouton pour trouver le MST, mais il se concentre sur les arêtes plutôt que sur les sommets.

Étapes de l'Algorithme de Kruskal

1. Trier toutes les arêtes du graphe par poids dans l'ordre non décroissant.
2. Initialiser l'ensemble MST (vide).
3. Itérer à travers les arêtes triées :
   • Pour l'arête actuelle (U, V), vérifier si U et V sont déjà connectés (c'est-à-dire dans le même composant).
   • S'ils ne sont pas connectés (l'ajout de l'arête ne créerait pas de cycle), ajouter l'arête à l'ensemble MST et combiner les deux composants.

Disjoint Set Union (DSU)

Kruskal's repose fortement sur la structure de données DSU (également connue sous le nom de Union-Find). DSU permet deux opérations O(α(N)) très efficaces (où α est la fonction inverse d'Ackermann, qui est presque un temps constant) :

1. Find : Déterminer à quel ensemble un élément appartient (utile pour la détection de cycle).
2. Union : Fusionner deux ensembles en un seul (utile pour ajouter une arête).

Cela rend Kruskal's très efficace, souvent O(E log E) dominé par le tri initial.