Graph Representation: Adjacency List

An adjacency list is a list of lists. Each list corresponds to a vertex $u$ and contains a list of vertices adjacent to it.

Here is an example for an undirected graph:

Here is an example for directed graph:

Incidence List

An incidence list is similar to adjacency list except that each vertex $u$ is mapped to a list of edges $(u, v)$ that is incident to $u$.

The space requirement for adjacency/incidence list representation is $O(N+M)$.

You need a list of vertices $O(N)$, and each vertex has a list of its adjacent vertices (or incident edges). The size of the list will be equal to the degree of that vertex. The total size is the sum of the degree of all vertices which is $2M$. (See "degree sum formula" discussed earlier.)