L'algorithme de Kruskal expliqué

Mohammed Islam Hadjoudj

Ingénieur expert en recherche opérationnelle

1. Introduction à l'algorithme de Kruskal

L'algorithme de Kruskal construit un arbre couvrant de poids minimal : à partir d'un graphe connexe, non orienté et pondéré, il sélectionne l'ensemble d'arêtes le moins coûteux qui touche tous les sommets sans former de cycle. Pour V sommets, cet ensemble contient toujours exactement V - 1 arêtes.

Là où l'algorithme de Prim fait croître un unique arbre connexe vers l'extérieur depuis un sommet de départ, celui de Kruskal ignore presque entièrement la connexité jusqu'à la fin. Il trie toutes les arêtes du graphe par poids, parcourt cette liste de la moins chère à la plus chère, et conserve chaque arête sauf si elle fermerait un cycle. Rien d'autre n'est consulté. Il n'y a ni sommet de départ ni notion de frontière.

La conséquence est que Kruskal passe l'essentiel de son exécution à tenir une forêt plutôt qu'un arbre : de nombreux petits fragments dispersés dans le graphe, qui croissent et fusionnent indépendamment, et ne se fondent en un seul arbre couvrant qu'avec la toute dernière arête acceptée. C'est cette différence de forme qui le fait se comporter autrement sur les graphes creux, sur une entrée non connexe et sous un profileur.

2. Pourquoi cela fonctionne : la propriété de cycle

La correction de Prim repose sur un théorème indiquant quelles arêtes il est sûr d'accepter. Kruskal passe tout autant de temps à rejeter des arêtes, il vaut donc la peine d'énoncer le théorème complémentaire qui justifie d'en écarter une.

La preuve reflète celle de la propriété de coupe. Supposons que l'arête la plus lourde e d'un cycle appartienne bel et bien à un arbre couvrant de poids minimal T. Retirer e de T le scinde en deux composantes. Le reste de ce cycle relie toujours ces deux composantes, donc une autre arête du cycle f les reconnecte. Remettez f à la place. Vous avez de nouveau un arbre couvrant et, puisque e était strictement la plus lourde, le nouvel arbre est strictement plus léger, ce qui contredit la minimalité de T.

Observez maintenant ce qui se passe quand Kruskal rejette une arête. Il atteint l'arête e et constate que ses deux extrémités sont déjà dans le même fragment. Cela signifie qu'un chemin existe déjà entre elles, bâti uniquement avec des arêtes acceptées plus tôt, donc avec des arêtes pas plus lourdes que e. Ajouter e fermerait un cycle sur lequel e est le membre le plus lourd. Par la propriété de cycle, l'écarter ne coûte rien.

Les arêtes acceptées sont sûres pour la même raison que celles de Prim. Lorsqu'une arête joint deux fragments distincts, elle est l'arête restante la moins chère traversant la coupe qui sépare un fragment de tout le reste, si bien que la propriété de coupe s'applique sans changement. Kruskal est glouton dans les deux sens à la fois, et les deux sens sont des théorèmes.

3. Comment la forêt fusionne

Concrètement, l'algorithme place au départ chaque sommet dans son propre fragment : V fragments, zéro arête. En parcourant la liste triée, il pose une seule question à chaque arête (u, v) :

• u et v sont-ils déjà dans le même fragment ? Alors l'arête fermerait un cycle. Écartez-la et passez à la suivante.
• Sont-ils dans des fragments différents ? Alors acceptez l'arête et fusionnez les deux fragments en un seul.

Chaque arête acceptée réduit le nombre de fragments d'exactement un. Partir de V fragments et finir à un seul signifie donc précisément V - 1 acceptations, ce qui constitue la condition d'arrêt. Une fois ce nombre atteint, toute arête restante de la liste sera à coup sûr rejetée, la boucle peut donc sortir plus tôt.

L'algorithme entier se réduit ainsi à une unique question de structure de données : comment tester « même fragment ? » et « fusionne ces deux fragments » rapidement, des millions de fois ? C'est exactement ce que fournit union-find.

4. Exécution pas à pas

Prenons le graphe à six sommets utilisé tout au long de notre guide des arbres couvrants de poids minimal. Ses neuf arêtes sont :

A-B 4    A-C 1    B-C 2
B-D 5    C-D 6    C-E 7
D-E 2    D-F 8    E-F 3

Les trier par poids donne l'ordre que l'algorithme parcourra réellement :

A-C 1   B-C 2   D-E 2   E-F 3   A-B 4   B-D 5   C-D 6   C-E 7   D-F 8

Chaque sommet commence seul, la forêt démarre donc comme {A} {B} {C} {D} {E} {F}.

1. A-C (1). Accepter. Fragments différents. La forêt devient {AC} {B} {D} {E} {F}. Total courant 1.
2. B-C (2). Accepter. B est seul, C est avec A. La forêt devient {ABC} {D} {E} {F}. Total 3.
3. D-E (2). Accepter. Remarquez que cela bâtit un fragment très loin du premier. La forêt devient {ABC} {DE} {F}. Total 5.
4. E-F (3). Accepter. La forêt devient {ABC} {DEF}. Total 8.
5. A-B (4). Rejeter. A et B sont déjà tous deux dans {ABC}, cela fermerait donc le cycle A-C-B-A. Écartée.
6. B-D (5). Accepter. Cette arête fait le pont entre les deux fragments restants. La forêt devient {ABCDEF}. Total 13.

Cinq arêtes acceptées pour six sommets : l'algorithme s'arrête sans jamais examiner C-D (6), C-E (7) ni D-F (8). L'arbre obtenu est A-C (1), B-C (2), D-E (2), E-F (3), B-D (5), pour un poids total de 13, exactement l'arbre que Prim trouve sur le même graphe.

L'étape 3 est le moment qui distingue cet algorithme. Prim n'aurait pas pu prendre D-E à ce stade, car aucune de ses extrémités ne touchait son arbre en croissance. Kruskal s'en moque : il démarre volontiers un second fragment, sans lien avec le premier, à l'autre bout du graphe, et se souciera plus tard de les relier. Et l'étape 5 montre la propriété de cycle à l'oeuvre, en rejetant précisément l'arête la plus lourde du cycle qu'elle aurait créé.

5. Union-find : la structure qui le rend rapide

La façon naïve de tester si deux sommets sont déjà reliés consiste à lancer un parcours depuis l'un pour voir si l'on atteint l'autre. Cela coûte O(V) par arête et tire tout l'algorithme vers O(V * E), soit pire que le tri qu'il était censé compléter.

Union-find, aussi appelée structure d'ensembles disjoints, répond aux deux questions en temps quasi constant. Elle maintient chaque fragment sous forme d'arbre de pointeurs vers le parent, avec un représentant à la racine, et expose deux opérations :

• find(x) renvoie le représentant du fragment de x. Deux sommets sont dans le même fragment exactement lorsque leurs représentants sont identiques.
• union(x, y) fusionne les deux fragments en rattachant une racine sous l'autre.

Deux optimisations la rendent assez rapide pour disparaître de l'analyse de complexité. L'union par rang rattache toujours l'arbre le plus court sous le plus haut, empêchant la structure de dégénérer en chaîne. La compression de chemin repointe directement vers la racine chaque noeud visité pendant un find, si bien que les recherches répétées deviennent moins chères à mesure que l'algorithme avance.

Avec les deux, une suite de m opérations sur n éléments coûte O(m α(n)), où α est la fonction inverse d'Ackermann. Elle croît si lentement qu'elle reste inférieure à 5 pour toute entrée tenant dans l'univers observable : le travail d'union-find dans Kruskal est donc en pratique linéaire en nombre d'arêtes.

6. Implémentation et pseudo-code

Comme union-find porte la difficulté, l'algorithme lui-même est court.

function Kruskal(V, edges):
    trier edges par poids croissant
    makeSet(v) pour chaque sommet v    // V fragments singletons
    mst = []

    for chaque arête (u, v, w) dans l'ordre trié:
        if find(u) != find(v):         // fragments différents
            union(u, v)
            mst.append((u, v, w))
            if size(mst) == V - 1:     // sortie anticipée : arbre complet
                break

    return mst

Deux détails méritent d'être défendus. Le break n'est pas requis pour la correction, puisque toute arête ultérieure serait de toute façon rejetée, mais sur un graphe dense il saute la majeure partie de la liste. Et le supprimer entièrement n'est pas un bogue : c'est ce qui en fait un algorithme de forêt couvrante de poids minimal, comme expliqué plus bas.

La comparaison find(u) != find(v) est le seul endroit où les cycles sont jamais considérés. Aucune détection explicite de cycle n'apparaît nulle part, et c'est là l'élégance de l'approche : la comptabilité de la connexité s'en charge implicitement.

7. Complexité en temps et en espace

• Tri : O(E log E). Cela domine tout le reste. Comme E < V2, on a log E < 2 log V, si bien que la borne s'écrit indifféremment O(E log V).
• Union-find : O(E α(V)). Au plus deux appels à find et un union par arête. Linéaire en pratique.
• Au total : O(E log E). Le tri et rien d'autre.
• Espace : O(V + E). Les tableaux de parent et de rang sont en O(V) ; la liste d'arêtes elle-même est en O(E).

Le coût étant concentré en un seul point, toutes les optimisations utiles s'attaquent au tri. Si les arêtes arrivent déjà triées, ou si les poids sont de petits entiers permettant un tri par base ou par comptage, l'algorithme entier tombe à O(E α(V)), très proche du linéaire. Un tri partiel ou un tas paresseux aide également : on a rarement besoin de l'ordre complet, car l'algorithme s'arrête généralement bien avant d'atteindre les arêtes les plus lourdes.

8. Kruskal contre Prim

Les deux sont gloutons, tous deux se justifient par la même paire de théorèmes, et sur un graphe à poids distincts tous deux renvoient le même arbre. Les différences pratiques découlent de ce que chacun garde connexe.

                 Kruskal                      Prim
structure        foret de fragments           un arbre en croissance
piloté par       liste d'aretes triee         file de priorite
exige            union-find                   tas (ou balayage V x V)
cout             O(E log E)                   O(E log V), dense O(V^2)
meilleur sur     graphes creux                graphes denses
non connexe      donne une foret couvrante    ne couvre qu'une composante

La règle pratique est la densité. Sur un graphe creux, E est petit, le tri est bon marché, et Kruskal l'emporte. Sur un graphe dense où E approche V2, trier environ V2 arêtes coûte O(V2 log V), tandis que Prim avec matrice d'adjacence tourne en O(V2) tout net et prend la tête.

9. Notes pratiques et pièges courants

Forêts couvrantes et graphes non connexes

C'est ici que Kruskal possède un véritable avantage structurel. Lancez-le sur un graphe non connexe et il n'atteindra tout simplement jamais V - 1 arêtes acceptées. Il épuise la liste d'arêtes, et ce qui reste est une forêt couvrante de poids minimal : l'arbre couvrant minimal de chaque composante connexe, calculé en une passe et sans traitement particulier.

Prim ne peut pas faire cela depuis un unique départ. Lancé sur un sommet, il couvre la composante de ce sommet puis s'arrête, renvoyant en silence un arbre qui paraît valide mais ne couvre qu'une partie du graphe. Récupérer le reste suppose de détecter le manque et de relancer depuis un sommet non visité, une fois par composante. Le compte est d'ailleurs le diagnostic : si Kruskal termine avec V - 1 arêtes acceptées, le graphe était connexe ; s'il en a accepté V - k, le graphe comptait k composantes.

Arbre couvrant de poids maximal

Triez par ordre décroissant plutôt que croissant et chaque ligne de l'algorithme reste valable. La propriété de cycle bascule en un argument de propriété de coupe sur des poids opposés, et vous obtenez l'arbre couvrant le plus lourd. Prendre l'opposé des poids et lancer l'algorithme inchangé fonctionne tout aussi bien.

Reverse-delete

L'image miroir de Kruskal : triez les arêtes de la plus lourde à la plus légère et supprimez chacune sauf si sa suppression déconnecte le graphe. Il se justifie par la même propriété de cycle lue à l'envers, et produit le même arbre. Il est rarement employé car le test de connexité après chaque suppression est bien plus coûteux qu'une requête union-find.

Poids ex aequo

Lorsque plusieurs arêtes partagent un poids, le graphe peut posséder plus d'un arbre couvrant minimal, et celui que vous obtenez dépend de la façon dont votre tri départage les égalités. L'exemple ci-dessus en contient une : B-C et D-E pèsent toutes deux 2. Les arbres obtenus sont tous également optimaux, si bien que tout test comparant à une liste d'arêtes figée est fragile. Comparez plutôt le poids total.

Boucles et arêtes multiples

Une boucle échoue toujours au test find(u) != find(v) et se trouve écartée automatiquement, elle ne demande donc aucun traitement particulier. Parmi des arêtes multiples, la moins chère est atteinte en premier et acceptée, les autres sont ensuite rejetées comme cycles. Kruskal se montre exceptionnellement tolérant aux entrées désordonnées.

10. Applications concrètes

Conception de réseaux et d'infrastructures

La motivation d'origine : relier un ensemble fixe de sites avec le moins de câble, de conduite ou de voie possible. La vision centrée sur les arêtes de Kruskal convient naturellement lorsque l'entrée arrive déjà sous forme de liste de liaisons candidates avec leurs coûts, ce qui est le format habituel de ces données.

Classification hiérarchique

Lancez Kruskal et notez l'ordre dans lequel les fragments fusionnent : vous avez effectué une classification ascendante à lien simple. La séquence des fusions est précisément le dendrogramme, et s'arrêter plus tôt à V - k arêtes laisse exactement k groupes. Cette équivalence explique pourquoi les arbres couvrants minimaux apparaissent si souvent en apprentissage non supervisé.

Segmentation d'images

En traitant les pixels comme des sommets et les différences d'intensité comme des poids d'arêtes, l'algorithme de segmentation de Felzenszwalb et Huttenlocher est pour l'essentiel Kruskal, doté d'un prédicat de fusion comparant la variation interne d'un fragment au poids de l'arête.

Conception de circuits et routage

Minimiser la longueur totale de piste entre des plots fixes est un problème d'arbre couvrant minimal, et la liste d'arêtes des tracés candidats est justement ce qu'un routeur a déjà sous la main.

11. Ressources académiques et histoire

Contrairement à l'algorithme de Prim, découvert indépendamment au moins trois fois, celui-ci possède une attribution nette.

• Joseph B. Kruskal (1956) l'a publié dans une note de trois pages, On the shortest spanning subtree of a graph and the traveling salesman problem, dans les Proceedings of the American Mathematical Society. L'article a paru un an avant celui de Prim et trente ans après celui de Borůvka.
• Otakar Borůvka (1926) avait posé et résolu le problème de l'arbre couvrant minimal des décennies plus tôt, en planifiant l'électrification de la Moravie rurale.
• Robert Tarjan (1975) a démontré la borne amortie quasi constante pour union-find avec union par rang et compression de chemin, ce qui fixe à O(E α(V)) la part non consacrée au tri dans le coût de Kruskal.

Pour l'histoire complète de l'attribution du problème, voyez Graham et Hell. Pour des preuves rigoureuses des propriétés de coupe et de cycle ainsi que des deux algorithmes, la référence standard est Cormen, Leiserson, Rivest et Stein, Introduction to Algorithms, au chapitre sur les arbres couvrants de poids minimal. Les références complètes figurent à la fin de cet article.