Graph Representations

Understand the different data structures used to implement graph algorithms.

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 11 and VV. 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 uvuv is stored twice, once in usu’s neighbor list and once in vsv’s neighbor list; for directed graphs, each edge uvu\rightarrow v is stored only once, in the neighbor list of the tail uu. For both types of graphs, the overall space required for an adjacency list is O(V+E)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 vv in O(1+deg(v))O(1 + deg(v)) time; just scan vv’s neighbor list. Similarly, we can determine whether uvu\rightarrow v is an edge in O(1+deg(u))O(1 + deg(u)) time by scanning the neighbor list of uu. For undirected graphs, we can improve the time to O(1+min{deg(u),deg(v))}O(1 + min\left \{{deg(u), deg(v)})\right\} by simultaneously scanning the neighbor lists of both uu and vv, 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