Représentations des graphes par des listes
Représentation d'un graphe par la liste des arcs
C'est en fait la représentation qui correspond à la définition originale d'un graphe, c'est-à-dire liste des points et liste des arêtes.
La liste des points est facultative. On a numéroté les points de 1 à n, mais on aurait pu également les désigner par des noms que l'on aurait alors utilisés dans la liste des arcs.
Si des valeurs étaient associées aux arcs, on utiliserait à la place des couples (i,j) des u-plets (i, j, v1, v2, ...).
Avantages et inconvénients de la liste d'arcs par rapport aux représentations matricielles
Lorsque le graphe est pauvre en arcs, c'est sûrement la représentation qui utilise le moins de place en mémoire.
C'est la meilleure représentation pour les algorithmes qui utilisent des listes (triées ou non par valeurs) des arcs ou des arêtes, comme, par exemple, la méthode de point fixe dans ce module ou la recherche des arbres minimaux par l'algorithme de Kruskal dans le module plus avancé sur les algorithmes de graphe.
Par contre, il faut balayer la liste des arcs pour savoir si un arc existe ou non, même chose pour trouver les prédécesseurs ou les successeurs d'un point.
Remarque :
Dans toute la partie représentation des graphes par des listes, il faut cliquer sur les triangles associés à Précédent et Suivant pour changer de graphes.
Ce sont les mêmes graphes et la même mise en forme pour toutes les animations de manière à pouvoir effectuer des comparaisons entre les différentes représentations et les différentes implémentations.
En conséquence, pour les listes d'arcs, certaines listes sont coupées à droite pour les plus gros graphes.
IMPLÉMENTATION CONTIGUË DE LA LISTE DES ARCS
Les arcs sont numérotés et on utilise deux tableaux "origine" et "extrémité".
Si des valeurs étaient associées aux arcs, on ajouterait des tableaux "valeur1", "valeur2", ...
IMPLÉMENTATION CHAÎNÉE DE LA LISTE DES ARCS
On utilise un pointeur de début de liste qui pointe vers le premier arc, la représentation de chaque arc utilise trois cases, une case pour le numéro de l'origine, une case pour le numéro de l'extrémité et une case pour le pointeur vers l'arc suivant ou NIL.
La notion de pointeurs est proposée par tous les langages de programmation modernes.
IMPLÉMENTATION : avantages et inconvénients des implémentations des listes d'arcs contiguës et chaînées.
L'implémentation contiguë est plus simple et légèrement plus compacte (on gagne seulement la place des pointeurs).
Elle devient très mauvaise quand le problème conduit à modifier fréquemment la structure du graphe.
Représentation d'un graphe par les listes des successeurs des points
Cliquer sur les triangles qui suivent P ou qui précédent S pour faire tourner les exemples.
Avantages et inconvénients des listes de successeurs
Cette représentation permet d'explorer facilement les descendants des points.
Bien sûr, comme la liste des arcs, elle ne donne pas directement accès à l'existence ou non d'un arc donné. Néanmoins, il suffira d'explorer la liste des successeurs de l'origine de l'arc pour obtenir la réponse.
IMPLÉMENTATION contiguë des listes de successeurs des points
Si on veut réellement minimiser la mémoire utilisée pour cette représentation, on utilise un seul tableau "Successeurs" pour y ranger les numéros des successeurs de tous les points dans l'ordre des points. On utilise en outre deux tableaux d'entiers pour indiquer la position du premier et du dernier successeur d'un point, si le numéro du dernier successeur d'un point est strictement inférieur au numéro du premier successeur du point, cela signifie que le point n'a pas de successeurs.
IMPLÉMENTATION chaînée des listes de successeurs des points
On utilise des listes chaînées comme pour la liste chaînée des arcs. Il y a une liste chaînée de successeurs par point. Il y a une seule information dans la liste : le numéro des successeurs, sauf si on veut en outre stocker des valeurs associées aux arcs correspondant.
Représentation d'un graphe par les listes de prédécesseurs des points
Cliquer sur les triangles qui suivent P ou qui précédent S pour faire tourner les exemples.
Avantages et inconvénients des listes de prédécesseurs
Cette représentation permet d'explorer facilement les ascendants des points.
Bien sûr, comme la liste des arcs, elle ne donne pas directement accès à l'existence ou non d'un arc donné. Néanmoins, il suffira d'explorer la liste des prédécesseurs de l'extrémité de l'arc pour obtenir la réponse.
En fait, c'est la liste des successeurs du graphe inverse.
IMPLÉMENTATION contiguë des listes de prédécesseurs des points
Si on veut réellement minimiser la mémoire utilisée pour cette représentation, on utilise un seul tableau "Prédécesseurs" pour y ranger les numéros des prédécesseurs de tous les points dans l'ordre des points. On utilise en outre deux tableaux d'entiers pour indiquer la position du premier et du dernier prédécesseur d'un point, si le numéro du dernier prédécesseur d'un point est strictement inférieur au numéro du premier prédécesseur du point, cela signifie que le point n'a pas de prédécesseurs.
IMPLÉMENTATION chaînée des listes de prédécesseurs des points
On utilise des listes chaînées comme pour la liste chaînée des arcs. Il y a une liste chaînée de prédécesseurs par point. Il y a une seule information dans la liste : le numéro des prédécesseurs, sauf si on veut en outre stocker des valeurs associées aux arcs correspondant.
Représentation simultanée des listes de prédécesseurs et de successeurs
Bien que l'information donnée soit redondante, pour accélérer certains algorithmes, on peut représenter simultanément les listes de prédécesseurs et les listes des successeurs.
IMPLÉMENTATION chaînée des listes de successeurs et de prédécesseurs des points : représentation de matrices creuses
Lorsqu'un graphe est très riche en points, très pauvre en arcs, que ce graphe évolue au fur et à mesure des itérations d'un algorithme et que l'on veut utiliser facilement aussi bien la liste des prédécesseurs que la liste des successeurs, on peut utiliser un système de chaînage dit de représentation de matrice creuse.
Ce système consiste à mettre comme élément générique des listes les arcs sous la forme (i, j, val1(i,j), val2(i,j) ...). et de munir chaque arc (i,j) de deux pointeurs.
Un pointeur "Suivant_ligne" qui indique la première case suivante non nulle sur la ligne i de la matrice en variables 0-1 (successeur suivant de i) ou Nil si j était le dernier successeur de i.
Un pointeur "Suivant_colonne" qui indique la première case suivante non nulle sur la colonne j de la matrice en variables 0-1 (prédécesseur suivant de i) ou Nil si i était le dernier prédécesseur de j.
Un tableau "Premier_succ" contient des pointeurs vers le premier successeurs de tout point i ou NIL si le point i n'a pas de successeur.
Un tableau "Premier_pred" contient des pointeurs vers le premier prédécesseurs de tout point j ou NIL si le point j n'a pas de prédécesseur.
Remarque : IMPLÉMENTATIONS doublement chaînée
Soit un graphe pour lequel on a attribué une valeur V(i,j) à chacun de ses arcs.
Si on souhaite visiter l'une quelconque des listes précédentes (liste de tous les arcs ou liste des successeurs de i ou liste des prédécesseurs de j) tantôt par ordre croissant des valeurs et tantôt par ordre décroissant des valeurs, on peut munir les listes de deux pointeurs : un pointeur vers le point suivant et un pointeur vers le point précédent. En outre, on dispose d'un pointeur vers la tête de la liste (premier élément) et d'un pointeur vers la queue de la liste (dernier élément).
Cette représentation doublement chaînée permet d'ajouter ou d'enlever plus facilement des éléments dans les listes lorsque la structure du graphe évolue souvent au cours d'un algorithme.
Cette représentation doublement chaînée peut être utilisée pour les matrices creuses, elles auront alors quatre pointeurs : précédent et suivant pour les successeurs et précédent et suivant pour les prédécesseurs.
