# Graph Representations

Understand the different data structures used to implement graph algorithms.

## We'll cover the following

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.

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy