AnalyseMéthode · Glossaire
algorithme de Kruskal
Algorithme de théorie des graphes permettant de déterminer un arbre couvrant de poids minimum dans un graphe pondéré. Étant donné un graphe de n sommets dont les arêtes sont triées par ordre de poids croissant, l'algorithme procède comme suit : on initialise l'ensemble T sans aucune arête. Lorsque n = 1, cet ensemble vide est déjà un arbre couvrant de poids 0. Sinon, à chaque étape k, on examine l'arête uₖ suivante dans la liste ordonnée ; si elle ne forme pas de cycle avec les arêtes déjà sélectionnées dans T, elle est ajoutée à T. L'algorithme s'arrête lorsque T contient exactement n − 1 arêtes, constituant ainsi un arbre couvrant.
Sommaire
Ce que vous allez apprendre
- Suivre le tri croissant des arêtes et le test qui empêche la formation d'un cycle.
- Construire sur cinq sommets un arbre de quatre arêtes et vérifier son poids total égal à 13.
- Reconnaître le rôle de la connexité et le résultat obtenu lorsque le graphe est non connexe.
- Distinguer Kruskal de Prim, d'un plus court chemin et d'un arbre couvrant non minimal.
- Traiter correctement les poids égaux, les boucles et les arêtes parallèles.
En clair
Imaginez cinq villes reliées par des routes de coûts différents. Il faut que toutes puissent communiquer, mais sans payer de liaison superflue. L'algorithme de Kruskal commence par la route la moins coûteuse, puis considère les suivantes par coût croissant.
Une route est retenue seulement si elle relie deux groupes encore séparés. Si elle referme une boucle, elle est écartée. Quand toutes les villes sont reliées, les routes choisies forment un réseau sans cycle dont le coût total est minimal.
Définition
L'algorithme de Kruskal est une méthode gloutonne appliquée à un graphe non orienté pondéré. Un poids est associé à chaque arête. Lorsque le graphe est connexe, la méthode produit un arbre couvrant de poids minimum : un ensemble d'arêtes qui relie tous les sommets, ne contient aucun cycle et minimise la somme des poids. Si T désigne l'arbre obtenu et w(e) le poids d'une arête e, son poids total est .
Les arêtes sont examinées par poids croissant. L'arête courante est ajoutée si ses deux extrémités appartiennent à deux composantes distinctes des arêtes déjà retenues ; elle est rejetée sinon, car elle fermerait un cycle. La construction s'arrête après n − 1 choix pour un graphe de n sommets.
Des poids égaux peuvent être départagés dans n'importe quel ordre : le poids minimal final est conservé, mais plusieurs arbres couvrants minimaux peuvent exister. Si le graphe n'est pas connexe, Kruskal ne peut pas produire un arbre couvrant unique de tous les sommets ; il renvoie une forêt couvrante minimale, une par composante connexe.
Le principe
Pour un graphe non orienté, pondéré et connexe, triez les arêtes par poids croissant et partez d'un ensemble T vide. Examinez chaque arête e dans cet ordre. Si ses extrémités sont dans deux composantes distinctes de T, effectuez ; sinon, rejetez e. Arrêtez dès que T compte n − 1 arêtes, où n est le nombre de sommets. Alors T est un arbre couvrant de poids minimum.
Quand l'utiliser
La donnée doit être un graphe non orienté dont chaque arête possède un poids dans un domaine additif ordonné, par exemple les nombres réels, afin que les poids puissent être triés et leur somme comparée. Des poids négatifs sont permis : seul leur ordre intervient dans les choix de Kruskal. Pour obtenir un arbre couvrant de tous les sommets, le graphe doit être connexe. À chaque étape, il faut aussi pouvoir déterminer si les deux extrémités de l'arête courante sont déjà reliées.
Un graphe orienté sort de ce cadre : ignorer le sens des arcs changerait le problème, et il faut employer une méthode d'arborescence orientée. Dans un graphe non connexe, l'arrêt à n − 1 arêtes est impossible ; on poursuit jusqu'à épuisement des arêtes et l'on obtient une forêt couvrante minimale.
Un exemple, pas à pas
Considérons cinq sommets A, B, C, D et E. Les huit arêtes, déjà classées par poids croissant, sont AB : 1, BC : 2, AC : 3, BD : 4, CD : 5, CE : 6, DE : 7 et AE : 8. Il faut retenir quatre arêtes, car n − 1 = 5 − 1 = 4.
1. AB, de poids 1, puis BC, de poids 2, relient successivement A, B et C. Elles sont retenues.
2. AC, de poids 3, est rejetée : A et C sont déjà reliés par A–B–C, donc AC fermerait le cycle A–B–C–A. BD, de poids 4, est ensuite retenue et rattache D.
3. CD, de poids 5, est rejetée, car C et D sont déjà reliés par C–B–D. CE, de poids 6, rattache enfin E. La figure distingue les quatre choix des deux refus qui suffisent avant l'arrêt.
L'arbre obtenu contient AB, BC, BD et CE. Son poids total vaut 1 + 2 + 4 + 6 = 13. Le contrôle structurel est refaisable : cinq sommets sont tous reliés par quatre arêtes sans cycle. Les arêtes DE et AE, plus lourdes, ne sont pas examinées puisque l'arbre est déjà complet.
En pratique
Pour concevoir un réseau de câbles, de routes ou de canalisations, Kruskal s'emploie lorsque chaque liaison possible a un coût et que seule la connexion globale compte. Il fournit alors une ossature sans boucle inutile.
En programmation, une structure d'ensembles disjoints, souvent appelée union-find, indique rapidement si les extrémités d'une arête appartiennent déjà au même groupe. Elle évite de rechercher un cycle complet après chaque ajout.
Kruskal est particulièrement naturel lorsque la liste d'arêtes est disponible et que le graphe est peu dense. Si l'on dispose plutôt d'un voisinage dense autour de chaque sommet, l'algorithme de Prim peut être plus commode à mettre en œuvre.
À ne pas confondre
Avec l'algorithme de Prim. Sur un graphe non orienté, pondé et connexe, les deux méthodes produisent un arbre couvrant minimal, mais leur geste diffère. Prim agrandit un seul arbre depuis un sommet ; Kruskal fusionne plusieurs composantes en choisissant globalement les arêtes les moins lourdes.
Avec un algorithme de plus court chemin. Un plus court chemin minimise le coût entre une origine et une destination, sans devoir relier tous les sommets. Kruskal optimise au contraire le poids total d'un arbre couvrant. Le chemin entre deux sommets dans cet arbre n'est donc pas nécessairement le plus court du graphe initial.
Avec n'importe quel arbre couvrant. Un ensemble connexe de n − 1 arêtes est bien un arbre couvrant, mais il n'est minimal que si aucun autre arbre couvrant n'a un poids total plus faible.
Limites et pièges
Graphe non connexe. Si deux groupes de sommets ne sont reliés par aucune arête, le compteur reste sous n − 1. Il ne faut pas annoncer un arbre couvrant : le résultat est une forêt couvrante minimale.
Poids égaux. Plusieurs arêtes peuvent occuper le même rang. Un ordre quelconque entre elles conserve un poids total minimal, mais pas forcément le même arbre. Il ne faut donc pas conclure à l'unicité sans argument supplémentaire.
Test local trompeur. Une arête n'est pas refusée parce qu'un triangle est visible à proximité, mais parce que ses deux extrémités sont déjà reliées dans la forêt retenue. Le bon test porte sur les composantes, même si le chemin existant est long.
Boucles et arêtes parallèles. Une boucle relie un sommet à lui-même et crée immédiatement un cycle ; elle est toujours rejetée. Entre deux sommets reliés par plusieurs arêtes, la première admissible peut rendre les suivantes inutiles.
Pour aller plus loin
arbre couvrant — Précisez la structure que Kruskal cherche et le rôle des n − 1 arêtes.
Graphe pondéré — Retrouvez la donnée de poids qui permet de classer les arêtes et d'évaluer l'arbre final.
algorithme — Replacez cette procédure gloutonne parmi les suites finies d'instructions conçues pour résoudre un problème.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres