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 u1}.
Au départ T={u1}.
A l’étape k, l’arête uk}. 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.