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, ainsi
qu'une représentation en mémoire de ce graphe sous forme
d'application ``successeurs'' (notée gamma ou Γ ).
On notera qu'en plus du graphe, des valeurs sont associées aux
arcs (en rouge).
Tous
les champs de la structure graphe ne sont pas encore
utilisés, seuls les champs utiles ici sont illustrés ici.
 |
 |
| (a) |
(b) |
Figure 1:
(a): un graphe; (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.