Algorithme de Kruskal

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

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'ARPM 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 consiste à d'abord ranger par ordre de poids croissant les arêtes d'un graphe, puis à retirer une à une les arêtes selon cet ordre et à les ajouter à l'ACM cherché tant que cet ajout ne fait pas apparaître un cycle dans l'ACM.

Algorithme[modifier | modifier le code]

Pseudo-code et explications[modifier | modifier le code]

KRUSKAL (G,w)
1 E := ø
2 pour chaque sommet v de G
3   faire CRÉER-ENSEMBLE (v)
4 trier les arêtes de G par ordre croissant de poids w
5 pour chaque arête (u,v) de G prise par ordre de poids croissant
6   faire si ENSEMBLE-REPRÉSENTATIF (u)  ENSEMBLE-REPRÉSENTATIF (v)
7           alors ajouter l'arête (u,v) à l'ensemble E
8                 UNION (u,v)
9 retourner E

w est une fonction qui associe à chaque arête du graphe G une valeur qui est son poids.

Les fonctions ENSEMBLE-REPRÉSENTATIF et UNION sont les deux opérations d'une structure Union-Find (qui, respectivement, renvoie un élément représentatif d'un ensemble et fusionne deux ensembles).

On remarquera que lors du déroulement de l'algorithme, l'ACM n'est pas nécessairement connexe, il ne le sera qu'à la fin.

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.

Voir aussi[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

Articles connexes[modifier | modifier le code]