Graph representation

Two common ways to represent graphs on a computer are as an adjacency list or as an adjacency matrix.

Adjacency list:

Vertices are labelled (or re-labelled) from 0 to $\vert V(G)\vert - 1$. Corresponding to each vertex is a list (either an array or linked list) of its neighbours.

Adjacency matrix:

Vertices are labelled (or re-labelled) with integers from 0 to $\vert V(G)\vert - 1$. A two-dimensional boolean array $A$ with dimensions $\vert V(G)\vert \times \vert V(G)\vert$ contains a 1 at $A[i][j]$ if there is an edge from the vertex labelled $i$ to the vertex labelled $j$,and a 0 otherwise.

Both representations allow us to represent directed graphs, since we can have an edge from $v_i$ to $v_j$, but lack one from $v_j$ to $v_i$. To represent undirected graphs, we simply make sure that are edges are listed twice: once from $v_i$ to $v_j$, and once from $v_j$ to $v_i$.

Which representation is best? Both. If graph $G$ has a large portion of its edges, then the adjacency matrix doesn't waste much space, and it indicates whether edge $(i,j)$ exists with one access (rather than following a list). However, if graph $G$ is sparse (not many of its vertex pairs have edges between them), then an adjacency list becomes preferable. For example, if $G$ has 10,000 vertices and only about 20,000 edges, then its adjacency matrix representation will need $10^8$ (100 million) entries -- 400 megabytes if each took a word. Representing the same $G$ with an adjacency list might require, say, 10,000 words for the node plus 20,000 words for the list of neighbours: 30,000 words or 120K. The difference may make one representation feasible and the other infeasible.