algorithme de Kruskal

CALCUL
COMBINATOIRE

Algorithme de théorie des graphes :
Un graphe composé de n sommets est donné par la liste de ses arêtes dans l’ordre de leur poids croissant.
L’algorithme détermine un arbre recouvrant T de poids minimum.

Méthode:
La liste des arêtes est lue en commençant par l’arête de plus faible poids, notée u₁}.
Au départ T={u₁}.
A l’étape k, l’arête u_k}. est lue. Si elle ne forme pas de cycle avec les arêtes de T alors elle est retenue. L’algorithme s’arrête quand le nombre d’arêtes de T est égal à n-1.