Algorithme de Kruskal

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Arbre couvrant de poids minimum.

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 valué et non-orienté. Il a été conçu en 1956 par Joseph Kruskal.

Description du problème[modifier | modifier le code]

Quand on travaille sur un graphe connexe, certains problèmes obligent à transformer ce graphe en un arbre (graphe sans cycle élémentaire) qui contient tous les sommets du graphe et quelques arêtes. On dit alors qu'on a un « arbre couvrant » du graphe.

Exemples :
Simplifier un câblage

Parfois, lorsque le graphe est valué, il s'agit de chercher un arbre recouvrant de poids minimum, c'est-à-dire dont la somme des poids est minimale.

Exemples :
Supprimer les liaisons maritimes les moins rentables en préservant l'accessibilité aux différents ports.

L'arbre couvrant minimum contient tous les sommets du graphe qu'il recouvre et uniquement les arêtes qui assurent son acyclicité et le poids minimum possible.

Principe[modifier | modifier le code]

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'elle, il la sélectionne si elle ne crée pas un cycle.

Exemple[modifier | modifier le code]

Image Description
Kruskal Algorithm 1.svg AD et CE sont les arêtes de poids les plus faibles, ici 5. AD est sélectionnée de manière arbitraire.
Kruskal Algorithm 2.svg CE est l'arête suivante de poids le plus faible. Elle est sélectionnée car elle ne forme pas de cycle.
Kruskal Algorithm 3.svg L'arête DF de poids 6 est ensuite choisie.
Kruskal Algorithm 4.svg 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.
Kruskal Algorithm 5.svg 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.
Kruskal Algorithm 6.svg 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[modifier | modifier le code]

Pseudo-code et explications[modifier | modifier le 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   retourner 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é[modifier | modifier le code]

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[modifier | modifier le code]

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Kruskal's algorithm » (voir la liste des auteurs).

Voir aussi[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction à l'algorithmique, Dunod,‎ [détail de l’édition]

Articles connexes[modifier | modifier le code]