Gamma
Représentation d'un graphe par son application Gamma
Étudions, à partir de quelques exemples, la structure de
données
graphe (définie dans le fichier graphes.h). La
figure 1 montre un graphe simple, ainsi
qu'une représentation en mémoire de ce graphe sous forme
d'application ``successeurs'' (notée gamma ou Γ ). Tous
les champs de la structure graphe ne sont pas encore
utilisés, seuls les champs utiles ici sont illustrés.
![](ex1_1.gif) |
![](ex1_2.gif) |
(a) |
(b) |
Figure 1:
(a): un graphe simple; (b): une représentation en mémoire
de ce graphe sous forme d'application Γ.
Notez qu'il est prévu de réserver pour les arcs du graphe
plus de place que nécessaire (narc), ce qui permet de modifier un graphe en lui
retirant ou en lui rajoutant des arcs (dans la limite de nmaxarc).
Dans cet exemple, il reste de la place pour stocker deux arcs supplémentaires.
Les cellules de liste (de type cell) sont allouées en une seule fois à
l'initialisation de la structure et stockées dans le tableau
reserve, pour éviter des appels répétés
(et coûteux) à la fonction système malloc ou new.