Adjacency list format (graph)
programming
Adjacency list
For a graph $G = (V,E)$ (that can be a directed graph or undirected graph) the adjacency list format is a list of neighbourhoods $N_v = \{u \in V \vert (v,u) \in E\}$ for $v \in V$.
- This takes up $O(\vert V \vert + \vert E \vert)$ space as you need to store the vertices $V$ and lists of edges taking up $2\vert E \vert$ space.
- To check if two vertices are connected takes $O(\vert N_v \vert)$ time.
- Finding neighbours takes $O(\vert N_v \vert)$.