Algorithme de Kruskal
En informatique, l'algorithme de Kruskal est un algorithme de recherche d'arbre recouvrant de poids minimum (ARPM) ou arbre couvrant minimum (ACM) dans un graphe connexe non-orienté et pondéré. Il a été conçu en 1956 par Joseph Kruskal.
Description du problème
On considère un graphe connexe non-orienté et pondéré ː chaque arête possède un poids qui est un nombre qui représente le coût de cette arête. Dans un tel graphe, un arbre couvrant est un sous-graphe connexe sans cycle qui contient tous les sommets du graphe. Le poids d'un tel arbre est la somme des poids des arêtes qui le compose. Un arbre couvrant minimum est un arbre couvrant dont le poids est inférieur ou égal à celui de tous les autres arbres couvrants du graphe. L'objectif de l'algorithme de Kruskal est de calculer un tel arbre couvrant minimum.
Ce problème a de nombreuses applications, par exemple simplifier un câblage ou supprimer les liaisons maritimes les moins rentables en préservant l'accessibilité aux différents ports.
Principe de l'algorithme
L'algorithme construit un arbre couvrant minimum en sélectionnant des arêtes par poids croissant. Plus précisément, l'algorithme considère toutes les arêtes du graphe par poids croissant (en pratique, on trie d'abord les arêtes du graphe par poids croissant) et pour chacune d'elles, il la sélectionne si elle ne crée pas un cycle. Le tableau suivant donne un exemple d'exécution de l'algorithme de Kruskal.
| Image | Description |
|---|---|
|
AD et CE sont les arêtes de poids les plus faibles, ici 5. AD est sélectionnée de manière arbitraire. |
|
CE est l'arête suivante de poids le plus faible. Elle est sélectionnée car elle ne forme pas de cycle. |
|
L'arête DF de poids 6 est ensuite choisie. |
|
Les arêtes de poids faibles (7) suivantes sont AB et BE. AB est choisie de manière arbitraire. L'arête BD est dessinée en rouge car il existe un chemin (en vert) entre B et D. BD ne sera donc jamais sélectionnée. |
|
La prochaine arête considérée est BE de poids 7. BC ne sera jamais choisie car la choisir formerait le cycle BCE. De même DE formerait le cycle DEBA et FE formerait le cycle FEBAD. |
|
Finalement, l'arête EG de poids 9 est choisie et un arbre couvrant minimum est trouvé (en vert). |
On remarque que lors du déroulement de l'algorithme, les arêtes sélectionnées ne forment pas nécessairement un graphe connexe. Mais à la fin, les arêtes sélectionnées (en vert) forment un graphe connexe.
Algorithme
Pseudo-code
Kruskal(G) : 1 A := ø 2 pour chaque sommet v de G : 3 créerEnsemble(v) 4 trier les arêtes de G par poids croissant 5 pour chaque arête (u, v) de G prise par poids croissant : 6 si find(u) ≠ find(v) : 7 ajouter l'arête (u, v) à l'ensemble A 8 union(u, v) 9 renvoyer A
Les fonctions créerEnsemble, find et union sont les trois opérations d'une structure de données Union-Find – qui, respectivement, ajoute une classe singleton à la structure, renvoie un représentant de la classe d'un élément et fusionne deux classes d'équivalence.
Complexité
La complexité de l'algorithme, dominée par l'étape de tri des arêtes, est Θ(A log A) avec A le nombre d'arêtes du graphe G.
Référence
Voir aussi
Bibliographie
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction à l'algorithmique, Dunod, [détail de l’édition]
