L'objectif de ce TP est d'implémenter l'algorithme de Kruskal.
Modifier le module de gestion des graphes pour qu'il gère les graphes non orientés avec arêtes pondérées
Qu'est qu'une forêt couvrante de poids minimal?
On considère le graphe non orienté valué
suivant:
Déterminer un arbre recouvrant de
de poids minimum depuis le sommet
en utilisant l'algorithme de Kruskal.
Rappel:
KRUSKAL(G)
E = {}
pour chaque sommet v de G faire
CREER_ENSEMBLE( v )
trier les arêtes de G par ordre croissant de poids w
pour chaque arête (u,v) de G pris par ordre de poids croissant faire
si TROUVER_ENSEMBLE(u) <> TROUVER_ENSEMBLE( v )
E = E + { (u,v) }
FUSIONNER_ENSEMBLE( u,v )
retourner E
Implémenter l'algorithme de Kruskal.
Ce TP est inspiré du TP TD 4 et des TDs donnés au Licences Informatiques INF351 de l'Université Bordeaux 1.