adjacency list

Adjacency list

Adjacency matrices are usually quite sparse, wasting space and compute.
We can instead also store the graph as an adjacency list, where we store $n_{\text{edges}}$ tuples of $(i,j)$, the $k$-th entry describing the edge $e_k$ between nodes $n_i$ and $n_j$.

$$O(n_{\text{edges}})<O(n_{\text{nodes}}^2)\text{ for }{n}_{\text{edges}}<\frac{n_{\text{nodes}}^2}{2}$$

In other words, it grows with the number of existing edges rather than the number of possible edges!
This format is also permutation invariant!