Liste d'adjacence
From Wikipedia, the free encyclopedia
En algorithmique, une liste d'adjacence est une structure de données utilisée pour représenter un graphe.
Cette représentation est particulièrement adaptée aux graphes creux (c'est-à-dire peu denses), contrairement à la matrice d'adjacence adaptée aux graphes denses.
La liste d'adjacence d'un graphe non orienté, est la liste des voisins de chaque sommet[1]. Celle d'un graphe orienté est typiquement, pour chaque sommet, la liste de nœuds à la tête de chaque arête ayant le sommet comme queue.
C'est une représentation relativement compacte lorsqu'il y a peu d'arêtes (graphe creux), puisque la liste globale contient 2m éléments, où m est le nombre d'arêtes.
Implémentations
Une représentation par liste d'adjacence d'un graphe associe, à chaque sommet du graphe, la collection de ses voisins, comme sommets ou comme arêtes. Il existe de nombreuses variations de ce principe de base, qui diffèrent par des détails dans la mise en œuvre de l'association entre les sommets et ces collections, et de l'implémentation de ces collections elles-mêmes, selon qu'elles comprennent, comme élément de base, les deux sommets des arêtes, ou les arêtes comme objet, ou seulement les sommets voisins, ou encore dans le choix des types d'objets utilisés pour représenter les sommets et la liste de arêtes.
Les représentations de graphes par liste d'adjacence privilégient une approche plus centrée sur les sommets. Il existe de nombreuses implémentations possibles de listes d'adjacence :
- L'implémentation en Python préconisée par Guido van Rossum utilise une table de hachage pour associer, à chaque sommet du graphe, la table des sommets adjacents. Dans cette représentation, un sommet peut être représenté par tout objet qui peut être haché. Il n'y a pas de représentation explicite des arêtes en tant qu'objets[2].
- Le livre de Cormen et al.[3] propose une implémentation dans laquelle les sommets sont représentés par les numéros d'index. Leur représentation utilise un tableau indexé par les numéros des sommets, dans lequel la cellule du tableau correspondant pointe vers une liste chaînée des sommets voisins de ce sommet. Dans cette représentation, les éléments de la liste chaînée peuvent être interprétés comme des arêtes; cependant, ils ne stockent pas les informations complètes sur chaque arête mais seulement l'autre extrémité de l’arête et, dans les graphes non orientés, il y aura deux éléments de liste chaînée différents pour chaque arête (un dans les listes pour chacune des deux extrémités de l'arête).
- En programmation orientée objet, la structure dite liste d'incidence suggérée par exemple par Goodrich and Tamassia dans leur livre[4] possède des classes d'objets pour les sommets et pour les arêtes. Chaque objet sommet a une variable d'instance pointant vers une collection qui répertorie les objets qui sont les arêtes incidentes. À son tour, chaque arête pointe vers les deux objets sommet qui sont ses extrémités. Cette version de la liste d'adjacence utilise plus de mémoire que la version dans laquelle les sommets adjacents sont listés directement, mais l'existence d'objets arête explicites permet une flexibilité accrue, par exemple pour l'enregistrement d'informations supplémentaires sur les arêtes.
Opérations
L'opération principale effectuée par la structure de données de liste d'adjacence est de fournir une liste des voisins d'un sommet donné. En utilisant l'une des implémentations décrites ci-dessus, cela peut être effectué en temps constant par voisin. En d'autres termes, le temps total pour énumérer tous les voisins d'un sommet est proportionnel au degré du sommet.
On peut également utiliser des listes d'adjacence pour tester si une arête existe entre deux sommets donnés, mais cette représentation n'est pas efficace. Dans une liste d'adjacence dans laquelle les voisins de chaque sommet ne sont pas triés, le test de l'existence d'une arête peut être réalisée en temps proportionnel au degré de l'un des deux sommets donnés, en utilisant un parcours séquentiel des voisins de ce sommet. Si les voisins sont représentés comme un tableau trié, une recherche dichotomique peut être utilisée à la place, en temps proportionnel au logarithme du degré.
