= Adjacency list
{title2=$\mathrm{Adj}[v]$}
{wiki}
An <adjacency list> represents a <graph> by keeping, for each <vertex> $v$, a collection $\mathrm{Adj}[v]$ of the <vertices> reached by its outgoing <edges>. An <array> indexed by <vertex> identifiers can locate each collection; the collection itself may use a <linked list> or an <array>. In an <undirected graph>, each nonloop <edge> supplies an entry at both endpoints.<Algorithms, 4th edition by Robert Sedgewick and others/Graph.java>[Graph.java, class documentation and fields: vertex-indexed adjacency collections; addEdge: entries at both endpoints]{ref}
For a worked example, take the <simple graph>
$$
V=\{A,B,C,D,E,F\},\qquad E=\{AB,AC,BC,CD,DE,DF,EF\},
$$
where $AB$ denotes the <unordered pair> $\{A,B\}$. Its <adjacency lists>, displayed in label order, are
$$
\begin{aligned}
\mathrm{Adj}[A]&=(B,C), & \mathrm{Adj}[B]&=(A,C), & \mathrm{Adj}[C]&=(A,B,D),\\
\mathrm{Adj}[D]&=(C,E,F), & \mathrm{Adj}[E]&=(D,F), & \mathrm{Adj}[F]&=(D,E).
\end{aligned}
$$
Thus $C$ has three <neighbours>, although the <graph> has six <vertices>. Its list contains exactly the destinations available for a single step from $C$; no slots are reserved there for $C,E,F$. The fourteen neighbour entries represent seven <edges>, with $CD$ appearing as $D$ in $C$'s list and as $C$ in $D$'s list. The label order makes the example easy to read; an <adjacency list> need not be sorted.
\Image[/adjacency-list-six-vertex-graph.png]
{title=Seven undirected <edges> and their fourteen <adjacency list> entries}
The useful idea is to store existing connections explicitly. <Neighbour enumeration> can then follow exactly the possible next steps, which is what <breadth-first search> and <depth-first search> need. In a <sparse graph>, most pairs of <vertices> have no <edge>; <adjacency lists> avoid reserving a separate <adjacency matrix> entry for every such absence. Whether this saves work depends on the question: <neighbour enumeration> and testing one proposed <edge> have different costs.
Back to article page
