# Glossary

## 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.