Time and Space Complexity

Complexité temporelle :

• Le tri des E arêtes est O(E log E) ; chaque opération union-find est presque O(1) avec la compression de chemin, donc l'algorithme de Kruskal classique est O(E log E). La version par sélection du minimum que nous construisons ici est O(E²), ce qui convient pour les petits graphes.

Complexité spatiale :

• O(V) pour le tableau parent (plus les arêtes d'entrée).

Résumé :

• Kruskal construit un MST en ajoutant l'arête la moins chère sans cycle à chaque étape, en utilisant union-find pour tester les cycles.
• Tous les MST partagent le même poids total, la réponse est donc unique.