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.
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[1].
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.
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.
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.
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é.
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.
Soit un graphe connexe pondéré et soit le sous-graphe de produit par l'algorithme. ne peut pas avoir de cycle, car par définition une arête n'est pas ajoutée si elle aboutit à un cycle. ne peut pas ne pas être connexe, car la première arête rencontrée qui joint deux composantes de aurait été ajoutée par l'algorithme. Ainsi, est un arbre couvrant de .
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.
De manière générale, la complexité de l'algorithme est Θ(S + E log E) + Θ(E(|find| + |union|)), avec E le nombre d'arêtes du graphe G, S le nombre de sommets, et |find| et |union| les complexités respectives des opérations de recherche et d'union de notre structure Union-Find.
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).