Graphs: Data Structure Representations

Graphs can be represented in various data structures, most commonly by either a list of lists or by an adjacency matrix.

List of Lists

In this representation of a graph, we have a list of vertices. In each vertex, we keep a list of the neighbors of each vertex.

Adjacency Matrix

In this representation of a graph, we keep a matrix $M$ whose $ij$th entry is $1$ if there is an edge from $V_i$ to $V_j$ and $0$ otherwise. There are two general observations we can make about all adjacency matrices: (1) they are symmetric, which means $M_{ij}=M_{ji}$ or $M=M^T$ in matrix terms (2) they have $0$s along the main diagonal, i.e., $M_{ii}=0$. Note that symmetry is broken if $M$ becomes directed, but that is a whole different story.