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 $$ ...