Adjacency List

graph-theory data-structures

Definition

Adjacency List

An adjacency list is a data structure used to represent a graph $G=(V,E)$ as a collection of unordered lists. Formally, for each vertex $v\in V$, the adjacency list $Adj[v]$ contains all vertices $u$ such that there exists an edge $(v,u)\in E$.

Computational Properties

Space Complexity: Requires $O(|V|+|E|)$ space, making it highly efficient for sparse graphs.

Lookup Efficiency: Finding all neighbours of a vertex $v$ takes $O(\text{deg}(v))$ time, while checking the existence of a specific edge $(u,v)$ also requires $O(\text{deg}(u))$ time.

Comparison: Unlike the adjacency matrix, the adjacency list does not require $O(|V{|}^2)$ storage, though edge lookups are generally slower for dense graphs.