Algo: Adjacency matrix

Let $G(V,E)$ be a graph with $|V|=n$ vertices. Its adjacency matrix is an $n \times n$ array whose $(i, j)$th entry is $$ a_{ij} = \begin{cases} 1 & \text{if there is an edge from $v_i$ to $v_j$}\\ 0 & \text{otherwise.}\\ \end{cases} $$

For undirected graphs, the matrix is symmetric since an edge $\{u, v\}$ can be taken in either direction. The biggest convenience of this format is that the presence of a particular edge can be checked in constant time, with just one memory access. On the other hand the matrix takes up $O(n^2)$ space, which is wasteful if the graph does not have very many edges.

Source: Algorithms by Dasgupta, Papadimitriou, Vazirani. McGraw-Hill. 2006.