TD 7 - Graphes
L'objectif du TD est d'implémenter les algorithmes dans les graphes vus en
cours. Afin de faciliter le test des algorithmes, le fichier
Graphe.cc contient:
- Une procédure LireGraphe qui lit dans un fichier une
description textuelle d'un graphe sous la forme d'une liste de transitions
(voir l'exemple ici) et qui retourne une liste
chaînée de triplets (string,double,string) (type
triplet_SDS). L'argument de LireGraphe est une chaîne
de caractères désignant le nom du fichier à lire.
- Un canevas de la glasse Graphe. Le constructeur
Graphe::Graphe(triplet_SDS * lt) construit le graphe selon la
procédure discutée en cours. Il utilise le type Ensemble
pour manipuler des ensembles de chaînes de caractères.
1.
A partir de ce canevas, il faut ajouter...
- l'algorithme de parcours en profondeur.
- l'algorithme de recherche des composantes fortement connexes.
- un algorithme des plus courts chemins depuis un sommet donné.
2.
Définir une classe GrapheM basée sur une représentation
matricielle et implémenter l'algorithme de Floyd.
fl@lsv.ens-cachan.fr
Last modification: January 23, 2002