adjacentiellijst

Een adjacentiellijst is een representatie van een grafiek waarbij voor elke knoop (vertex) een lijst wordt bijgehouden met de knopen waarnaar hij direct is verbonden. In een ongerichte grafiek bevat de lijst beide zijden van elke rand, terwijl in een gerichte grafiek de lijst meestal de uitgaande buren bevat. Het is een veelgebruikte datastructuur voor grafen, vooral wanneer de grafiek schaars is.

Een implementatie kan bestaan uit een array (of map) waarin per knoop een lijst van aangrenzende knopen staat. Deze lijsten kunnen bestaan uit gekoppelde lijsten, dynamische arrays of sets. Bij gerichte grafen bevat de lijst meestal alleen de buren waarnaar een rand wijst; bij ongerichte grafen staan de buren ook in de lijst van degene aan wie ze grenzen. Multigrafen kunnen extra informatie per rand toelaten.

Voordelen: efficiënte opslag voor grafen met relatief weinig randen; het doorlopen van de buren van een knoop is O(degraad(v)). Veelvoorkomende bewerkingen zijn: rand toevoegen (O(1) gemiddeld als men een append gebruikt), rand verwijderen (O(degraad(v)) in het slechtste geval), controleren of twee knopen aangrenzend zijn (O(degraad(v)) tenzij een set wordt gebruikt). Ruimtecomplexiteit is O(V+E).

Vergeleken met een adjacentiematrix gebruikt een adjacentiellijst minder geheugen bij grote aantallen knopen en relatief weinig randen; bij dicht verbonden grafen kan een matrix voordeliger zijn vanwege constante tijd voor het bestaan van een rand. Toepassingen omvatten netwerken en sociale netwerken, routeplanning en grafen waarin efficiënt itereren over de buren centraal staat.