Comparison of Graph Representations

After studying both adjacency matrices and adjacency lists, let’s see how they compare for common operations that we’ll perform in graph algorithms.

In most applications of graph algorithms, the set of nodes $V$ is constant. No nodes are added or removed over time. We can therefore focus on operations that work on the edge set $E$.

Memory usage

The adjacency matrix stores at least one bit for every ordered pair of nodes $(u, v)$. Since there are exactly $(|V|^2 - |V|)$ such pairs, the memory footprint is $\mathcal{O}(|V|^2)$.

The adjacency list representation needs to store one list for each node in the graph, which takes at least $\mathcal{O}(|V|)$ space. Additionally, every edge of the graph needs to be stored in one of the lists, taking up further $\mathcal{O}(|E|)$ space. The total memory requirements are thus $\mathcal{O}(|V| + |E|)$.

In most cases, the adjacency list representation is more memory efficient, as it stores only the present edges, while the adjacency matrix also contains entries for all absent edges. The two representations are comparable only in dense graphs. Note that in a dense graph, the number of edges is close to the maximum number of edges ($|V|^2-|V|$), so we have $|E| = \mathcal{O}(|V|^2)$.

Operations on single edges

Let’s assume that we are given two nodes $u, v$, and we want to perform an operation on the edge $(u,v)$, for example:

• Test whether the edge exists.
• Add or remove the edge.
• Modify the edge’s weight.