Structures de Données, Algorithmes 2

TP n° 3

(Graphes I)

Notions abordées : graphes, représentation des graphes, matrice d'adjacence, listes d'adjacence.

Représentation par matrice d'adjacence.

    On considère ici des graphes orientés simples finis et l'on souhaite représenter ces graphes et les opérations de base sur ces graphes en utilisant une matrice d'adjacence.  

1. Définir le type graphe. On fixera le nombre maximum de sommets du graphe et on utilisera une matrice de booléens.
2. Définir les constructeurs en respectant bien les préconditions :  Grnouv() (création d'un graphe vide), Adjs(x) (ajout d'un sommet), Adja(g,x,y) (ajout d'un arc).
3. Définir les transformateurs : sups(g,x) (suppression d'un sommet), supa(g,x,y) (suppression d'un arc).
4. Définir les observateurs : exs(g,x) (existence d'un sommet), exa(g,x,y) (existence d'un arc), di(g,x) (nombre d'arcs entrant en un sommet), de(g,x) (nombre d'arcs partant d'un sommet).
5. Tester vos fonctions en prenant l'exemple du graphe suivant :

Représentation par listes d'adjacence.

    On considère ici des graphes orientés simples finis et l'on souhaite les représenter en utilisant pour chaque sommet x la liste des sommets y tels qu'il existe une arc de x à y (liste d'adjacence).  On représentera le type abstrait des listes par des listes chaînées en utilisant des pointeurs (définition les opérations de base sur les listes).

    Répondre aux mêmes questions que dans la section précédente, mais en utilisant cette nouvelle représentation.