Algorithme de Kruskal

En informatique, l'algorithme de Kruskal est un algorithme de recherche d'arbre couvrant minimum (ACM) dans un graphe connexe non-orienté et pondéré. Dans un graphe non connexe, il construit une forêt dont chaque arbre est un arbre couvrant minimum d'une composante connexe.

Un arbre couvrant $T$ d'un graphe $G$ est un arbre (graphe acyclique) tel que l'ensemble des sommets de $T$ est le même que celui de $G$ : l'arbre « couvre » le graphe $G$ . Pour un graphe pondérée, un arbre couvrant minimal minimise la somme du poids des arrêtes. L'algorithme de Kruskal est un algorithme glouton, c'est-à-dire qu'à chaque étape il prend l’arrête de poids minimum ne formant pas un cycle^[1].

Le premier algorithme s'intéressant à la recherche d’un arbre couvrant minimale est publié par Otakar Borůvka en 1926. L’algorithme de Kruskal publié par Joseph Kruskal en 1956^[2]. Puis a était redécouvert par H. Loberman et A. Weinberger en 1957.

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^[3].

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 les étapes de l'algorithme n'ont pas pour but d'entretenir un graphe connexe tout au long de l'exécution, mais il est certain que nous convergerons vers un graphe connexe lorsque l'algorithme arrive au terme de son exécution.

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. Une amélioration possible est d'utiliser un tas à la place d'un tri afin de diminuer la complexité.

Preuve de correction

La preuve se compose de deux parties. Premièrement, il est prouvé que l'algorithme produit un arbre couvrant. Deuxièmement, il est prouvé que l'arbre couvrant construit est d'un poids minimal.

Arbre couvrant

Soit $G$ un graphe connexe pondéré et soit $Y$ le sous-graphe de $G$ produit par l'algorithme. $Y$ ne peut pas avoir de cycle, car par définition une arête n'est pas ajoutée si elle aboutit à un cycle. $Y$ ne peut pas ne pas être connexe, car la première arête rencontrée qui joint deux composantes de $Y$ aurait été ajoutée par l'algorithme. Ainsi, $Y$ est un arbre couvrant de $G$ .

Minimalité

Nous montrons que la proposition suivante 'P' est vraie par récurrence : Si F est l'ensemble des arêtes choisies à n'importe quel stade de l'algorithme, alors il y a un arbre couvrant minimum qui contient «F» ainsi qu'aucune des arêtes qui ont été rejetées par l'algorithme.

Clairement 'P' est vrai au début, quand F est vide: n'importe quel arbre couvrant minimum fera l'affaire, et il en existe un car un graphe connexe pondéré a toujours un arbre couvrant minimum .
Supposons maintenant que 'P' soit vrai pour un ensemble d'arêtes non final F et que T soit un arbre couvrant minimum contenant F .
- Si l'arête suivante choisie a est également dans T , alors 'P' est vrai pour F + a .
- Sinon, si a n'est pas dans T alors T + a a un cycle C. Ce cycle contient des arêtes qui n'appartiennent pas à F , puisque a ne forme pas un cycle lorsqu'il est ajouté à F mais le fait dans T . Soit b une arête qui est dans C mais pas dans F + a . Notons que b appartient également à T et n'a pas été pris en compte par l'algorithme. b doit donc avoir un poids au moins aussi grand que a . Puis T - b + a est un arbre, et il a le même poids ou moins que T . Donc T - b + a est un arbre couvrant minimum contenant F + a et encore une fois 'P' tient.

Par conséquent, selon le principe de récurrence, 'P' vaut quand F est devenu un arbre couvrant, ce qui n'est possible que si F est un arbre couvrant minimum lui-même.

Complexité

Une représentation naïve, utilisant des tableaux, aura donc une complexité en temps Θ(E x S), dominée par |find| = Θ(S) . Cette complexité se trouve fortement améliorée par une implémentation utilisant des arbres, passant à Θ(E log S). En compressant les chemins, on peut même atteindre une complexité amortie en temps Θ(E log* S).

Référence

(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).

Notes

↑ Cormen et al. 2002.
↑ R.L. Graham et Pavol Hell, « On the History of the Minimum Spanning Tree Problem », IEEE Annals of the History of Computing, vol. 7, n^o 1,‎ 1985, p. 43–57 (ISSN 1058-6180, DOI 10.1109/MAHC.1985.10011, lire en ligne, consulté le 29 octobre 2024)
↑ Cf. Alfred Aho, John Hopcroft et Jeffrey Ullman (trad. J.-M. Moreau), Structures de données et algorithmes, Paris, InterÉditions, 1995, 450 p. (ISBN 978-2-7296-0194-2), « Graphes non orientés », p. 238

Voir aussi

Bibliographie

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction à l'algorithmique, Dunod, 2002 [détail de l’édition]
(en) J. B. Kruskal, « On the shortest spanning subtree of a graph and the traveling salesman problem », Proceedings of the American Mathematical Society, vol. 7, n^o 1,‎ 1956, p. 48–50 (DOI 10.1090/S0002-9939-1956-0078686-7 , JSTOR 2033241)
(en) H. Loberman et A. Weinberger, « Formal Procedures for connecting terminals with a minimum total wire length », Journal of the ACM, vol. 4, n^o 4,‎ octobre 1957, p. 428–437 (DOI 10.1145/320893.320896 , S2CID 7320964)

Articles connexes

Portail de l'informatique théorique

[Cormen2frCormen_''<abbr_class="abbr_"_title="et_alii_(«_et_d’autres_»)"_lang="la">et_al.</abbr>''_2002-1] Cormen et al. 2002.

[2] R.L. Graham et Pavol Hell, « On the History of the Minimum Spanning Tree Problem », IEEE Annals of the History of Computing, vol. 7, n^o 1,‎ 1985, p. 43–57 (ISSN 1058-6180, DOI 10.1109/MAHC.1985.10011, lire en ligne, consulté le 29 octobre 2024)

[Aho-3] Cf. Alfred Aho, John Hopcroft et Jeffrey Ullman (trad. J.-M. Moreau), Structures de données et algorithmes, Paris, InterÉditions, 1995, 450 p. (ISBN 978-2-7296-0194-2), « Graphes non orientés », p. 238

[1]

[2]

[3]