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