Examen de TD n°2

$\parbox{120mm}{%% La durée de l'examen est de 60 minutes, les notes... ...uement à titre indicatif. Il pourra être modifié lors de la notation finale. }$

Cet examen porte sur la représentation de graphes orientés en C. Un graphe orienté $G=(S,A)$ est constitué d'un ensemble $S$ de sommets et d'un ensemble $A$ d'arêtes (c'est à dire de couples de sommets). On peut donc considérer qu'un sommet est connecté à un ensemble d'autres sommets (voir figure 1).

Figure: Un exemple de graphe orienté

Sur le graphe de la figure 1, les voisins du sommet étiqueté par $3$ sont donc lui-même, le sommet étiqueté par $2$ et le sommet étiqueté par $4$.

Les types utilisés dans cette épreuve seront les suivants:

typedef struct s_sommet_maillon *p_sommet_maillon_t;
typedef p_sommet_maillon_t       sommet_liste_t;
typedef sommet_liste_t          *p_sommet_liste_t;
typedef struct s_sommet         *sommet_t;

typedef struct s_sommet_maillon {
  sommet_t noeud;
  sommet_liste_t suivant;
} sommet_maillon_t;

typedef struct s_sommet {
  int etiquette;
  sommet_liste_t voisins;
} s_sommet_t;

Un sommet est donc composé d'une étiquette de type int et d'une liste de sommets qui sont ses voisins.