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.