13.2 Graph representations

There are two commonly used methods for representing graphs. The adjacency matrix for a graph is a $|\mathbf{V}| \times |\mathbf{V}|$ array. We typically label the vertices from $v_0$ through $v_{|\mathbf{V}|-1}$. Row $i$ of the adjacency matrix contains entries for vertex $v_i$. Column $j$ in row $i$ is marked if there is an edge from $v_i$ to $v_j$ and is not marked otherwise. The space requirements for the adjacency matrix are $O(|\mathbf{V}|^2)$.

The second common representation for graphs is the adjacency list. The adjacency list is an array of linked lists. The array is $|\mathbf{V}|$ items long, with position $i$ storing a pointer to the linked list of edges for vertex $v_i$. This linked list represents the edges by the vertices that are adjacent to vertex $v_i$.

Here is an example of the two representations on a directed graph. The entry for vertex 0 stores 1 and 4 because there are two edges in the graph leaving vertex 0, with one going to vertex 1 and one going to vertex 4. The list for vertex 2 stores an entry for vertex 4 because there is an edge from vertex 2 to vertex 4, but no entry for vertex 3 because this edge comes into vertex 2 rather than going out.

Both the adjacency matrix and the adjacency list can be used to store directed or undirected graphs. Each edge of an undirected graph connecting vertices $u$ and $v$ is represented by two directed edges: one from $u$ to $v$ and one from $v$ to $u$. Here is an example of the two representations on an undirected graph. We see that there are twice as many edge entries in both the adjacency matrix and the adjacency list. For example, for the undirected graph, the list for vertex 2 stores an entry for both vertex 3 and vertex 4.

The storage requirements for the adjacency list depend on both the number of edges and the number of vertices in the graph. There must be an array entry for each vertex (even if the vertex is not adjacent to any other vertex and thus has no elements on its linked list), and each edge must appear on one of the lists. Thus, the cost is $O(|\mathbf{V}| + |\mathbf{E}|)$.

Sometimes we want to store weights or distances with each each edge, such as in Figure 13.1 (c). This is easy with the adjacency matrix, where we will just store values for the weights in the matrix. In Figure 13.7 and Figure 13.8 we store a value of “1” at each position just to show that the edge exists. That could have been done using a single bit, but since bit manipulation is typically complicated in most programming languages, an implementation might store a byte or an integer at each matrix position. For a weighted graph, we would need to store at each position in the matrix enough space to represent the weight, which might typically be an integer.

The adjacency list needs to explicitly store a weight with each edge. In the adjacency list in Figure 13.9, each linked list node is shown storing two values. The first is the index for the neighbour at the end of the associated edge. The second is the value for the weight. As with the adjacency matrix, this value requires space to represent, typically an integer.

Which graph representation is more space efficient depends on the number of edges in the graph. The adjacency list stores information only for those edges that actually appear in the graph, while the adjacency matrix requires space for each potential edge, whether it exists or not. However, the adjacency matrix requires no overhead for pointers, which can be a substantial cost, especially if the only information stored for an edge is one bit to indicate its existence. As the graph becomes denser, the adjacency matrix becomes relatively more space efficient. Sparse graphs are likely to have their adjacency list representation be more space efficient.

The adjacency matrix often requires a higher asymptotic cost for an algorithm than would result if the adjacency list were used. The reason is that it is common for a graph algorithm to visit each neighbour of each vertex. Using the adjacency list, only the actual edges connecting a vertex to its neighbours are examined. However, the adjacency matrix must look at each of its $|\mathbf{V}|$ potential edges, yielding a total cost of $O(|\mathbf{V}^2|)$ time when the algorithm might otherwise require only $O(|\mathbf{V}| + |\mathbf{E}|)$ time. This is a considerable disadvantage when the graph is sparse, but not when the graph is closer to full.