Calculateur Algorithme de Kruskal

Pseudocode

Trie toutes les arêtes par poids, puis parcours la liste en ajoutant toute arête reliant deux composantes distinctes. Union-Find rend le test « composantes distinctes » pratiquement gratuit, ce qui est la clé de l'efficacité de l'ensemble.

Kruskal(graphe):
    trier toutes les aretes par poids croissant
    creerEnsemble(v) pour chaque sommet v
    acm = []

    pour chaque arete (u, v, w) dans l ordre trie:
        si trouver(u) != trouver(v):   // composantes distinctes
            unir(u, v)
            acm.ajouter((u, v, w))
            si acm a V - 1 aretes: sortir

    renvoyer acm

Kruskal fait croître une forêt, pas un arbre. Plusieurs fragments non connectés se développent indépendamment et fusionnent à mesure que des arêtes bon marché les relient, ce qui constitue la différence structurelle avec Prim et explique que Kruskal traite gratuitement les graphes non connexes: il renvoie simplement une forêt couvrante de poids minimum. La correction découle de la propriété de coupe appliquée aux frontières entre composantes, exactement comme pour Prim.

Exemple détaillé, étape par étape

Construis l'arbre couvrant de poids minimum sur le graphe déjà utilisé pour Prim, afin de comparer les deux ordres de découverte sur des données identiques.

Graphe d'exemple: Arêtes non orientées A-B (2), A-C (3), B-C (1), C-D (4) et B-D (7).

1. Trier les arêtes. Par poids: B-C à 1, A-B à 2, A-C à 3, C-D à 4, B-D à 7. Chaque sommet démarre dans son propre ensemble singleton.
2. Accepter B-C (1). B et C sont dans des ensembles distincts, l'arête est donc acceptée et les deux fusionnent. Les composantes sont maintenant {B, C}, {A} et {D}.
3. Accepter A-B (2). A et B sont encore dans des ensembles distincts, on accepte et on fusionne. Les composantes sont maintenant {A, B, C} et {D}.
4. Rejeter A-C (3). A et C appartiennent désormais au même ensemble, cette arête fermerait donc un cycle et se trouve écartée. C'est la différence visible avec Prim, qui n'a jamais fait remonter A-C comme candidate une fois les deux extrémités dans l'arbre.
5. Accepter C-D (4). C et D sont dans des ensembles distincts, on accepte et on fusionne. Les quatre sommets forment maintenant une seule composante et l'arbre compte trois arêtes, l'algorithme peut donc s'arrêter sans même examiner B-D à 7.

L'arbre couvrant de poids minimum est B-C, A-B et C-D pour un poids total de 1 + 2 + 4 = 7, identique à celui produit par Prim depuis A. Les arbres coïncident, comme ils le doivent lorsque les poids sont distincts, mais l'ordre de découverte diffère: Prim a suivi A-B, B-C, C-D en croissant vers l'extérieur depuis A, tandis que Kruskal a suivi B-C, A-B, C-D en pur ordre de poids et a dû rejeter explicitement une arête fermant un cycle en chemin. Cette différence d'ordre est visible dans le visualiseur et constitue la meilleure façon de saisir ce qui distingue réellement les deux algorithmes.

Complexité et son origine

Temps: O(E log E) · Espace: O(V + E)

Le tri des arêtes domine tout le reste avec O(E log E), ce qui équivaut à O(E log V) puisque E vaut au plus V au carré et que log E reste donc à un facteur constant de log V. Après le tri, la boucle effectue au plus 2E opérations de recherche et V - 1 unions. Avec compression de chemin et union par rang, chacune coûte la fonction d'Ackermann inverse de V, inférieure à 5 pour toute entrée tenant en mémoire et traitée comme constante. La partie Union-Find est donc effectivement en O(E) et le tri représente la totalité du coût. Lorsque les arêtes arrivent déjà triées, ou peuvent être réparties en seaux parce que les poids sont de petits entiers, Kruskal descend à quasi linéaire et bat nettement Prim.

Quand utiliser Algorithme de Kruskal, et quand l'éviter

Kruskal et Prim résolvent le même problème. La densité, l'ordre des arêtes et la connexité décident lequel est préférable.

Pièges fréquents

• Utiliser Union-Find sans compression de chemin ni union par rang. Une implémentation naïve dégénère en listes chaînées et chaque recherche devient O(V), poussant la boucle à O(E·V). Les deux optimisations tiennent en quelques lignes chacune et sont précisément ce qui rend réelle la borne quasi constante annoncée.
• Comparer des sommets au lieu de représentants d ensemble. Le test de cycle est trouver(u) != trouver(v), pas u != v. Comparer les sommets eux-mêmes accepte toutes les arêtes et produit un graphe rempli de cycles plutôt qu'un arbre, une erreur qui passe facilement inaperçue sur de très petits jeux de test.
• Oublier de s arrêter à V - 1 arêtes. Ce n'est pas un défaut de correction mais un coût inutile: dès que l'arbre compte V - 1 arêtes il est complet et toute arête restante sera rejetée. Sur un graphe dense cela représente une quantité considérable de parcours gaspillé.
• Supposer une réponse unique en cas d égalité de poids. Quand plusieurs arêtes partagent un poids, l'ordre du tri décide lesquelles sont retenues et des implémentations différentes produisent des arbres différents de même poids total. Vérifie le total, pas l'ensemble d'arêtes.
• L appliquer à des graphes orientés. Comme Prim, Kruskal est défini pour les graphes non orientés. L'analogue orienté est l'arborescence couvrante de poids minimum et nécessite l'algorithme de Chu-Liu/Edmonds.

Questions fréquentes

Comment fonctionne l'algorithme de Kruskal?

Il trie toutes les arêtes par poids puis parcourt la liste triée, ajoutant une arête chaque fois que ses deux extrémités appartiennent à des composantes distinctes et l'écartant lorsqu'elles sont déjà reliées. Une structure Union-Find répond à la question de connexité en temps quasi constant. Après V - 1 arêtes acceptées, le résultat est un arbre couvrant de poids minimum.

Quelle est la complexité temporelle de l'algorithme de Kruskal?

O(E log E) en temps, entièrement dominé par le tri des arêtes. Les opérations Union-Find n'ajoutent que O(E·α(V)), où α est la fonction d'Ackermann inverse et vaut pratiquement une constante. Si les arêtes sont déjà triées ou peuvent l'être par seaux, l'algorithme devient quasi linéaire.

Quelle est la différence entre les algorithmes de Kruskal et de Prim?

Kruskal considère les arêtes globalement par ordre de poids et fait croître une forêt qui fusionne en un arbre, en s'appuyant sur Union-Find pour rejeter les cycles. Prim fait croître un unique arbre connexe vers l'extérieur depuis un sommet de départ à l'aide d'une file de priorité. Kruskal convient aux graphes creux ou aux arêtes prétriées et gère nativement les entrées non connexes; Prim convient aux graphes denses.

Pourquoi Kruskal a-t-il besoin d'Union-Find?

Parce que la seule question qu'il pose à chaque arête est de savoir si ses extrémités sont déjà reliées, et cette question est posée E fois. Union-Find y répond en temps quasi constant avec compression de chemin et union par rang. Recalculer la connexité par un parcours pour chaque arête coûterait O(E·V) à la place.

Kruskal peut-il traiter un graphe non connexe?

Oui, sans modification. Il renvoie simplement une forêt couvrante de poids minimum, un arbre par composante connexe, car il n'exige jamais pendant son exécution que les arêtes acceptées forment une unique structure connexe. Prim, au contraire, s'arrête dès qu'il a épuisé la composante contenant son sommet de départ.