Graph Representations

In practice, graphs are usually represented by one of two standard data structures: adjacency lists and adjacency matrices. At a high level, both data structures are arrays indexed by vertices; this requires that each vertex has a unique integer identifier between $1$ and $V$. In a formal sense, these integers are the vertices.

Adjacency lists

By far, the most common data structure for storing graphs is the adjacency list. An adjacency list is an array of lists, each containing the neighbors of one of the vertices (or the out-neighbors if the graph is directed). For undirected graphs, each edge $uv$ is stored twice, once in $u’s$ neighbor list and once in $v’s$ neighbor list; for directed graphs, each edge $u\rightarrow v$ is stored only once, in the neighbor list of the tail $u$. For both types of graphs, the overall space required for an adjacency list is $O(V + E)$.

There are several different ways to represent these neighbor lists, but the standard implementation uses a simple singly-linked list. The resulting data structure allows us to list the (out-)neighbors of a node $v$ in $O(1 + deg(v))$ time; just scan $v$’s neighbor list. Similarly, we can determine whether $u\rightarrow v$ is an edge in $O(1 + deg(u))$ time by scanning the neighbor list of $u$. For undirected graphs, we can improve the time to $O(1 + min\left \{{deg(u), deg(v)})\right\}$ by simultaneously scanning the neighbor lists of both $u$ and $v$, stopping either when we locate the edge or when we fall off the end of a list.