Liste d'adjacence

thumb|Pour chaque sommet, la liste d'adjacence est représentée en jaune. 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. 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. 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. Le livre de Cormen et al. propose une implémentation dans laquelle les sommets sont représentés par les numéros d'index.