Minimum spaning tree (rbre couvrante minimum) : construire un arbre avec minimum de poids (kruskal algorithm)

Probléme d’optimisation : Contrainte pas de cyle et nombre d’arc = nombre nœud -1) avec chaque arc est une solution : 

les etapes 

1-      Trier les arcs par ordre décroissant sur leurs poids

2- Sélectionner le plus petit arc et verifier si il forme un cycle

3- Si il ne forme pas un cyle ajouter l’arc sinon eliminer l’arc

4- Répéter étape 2 jusquà le nombre d’arc V-1)

5- On arréte lorsque nombre d’arc=8

Weight   Src    Dest

1         7      6

2         8      2

2         6      5

4         0      1

4         2      5

6         8      6

7         2      3

7         7      8

8         0      7

8         1      2

9         3      4

10        5      4

11        1      7

14        3      5