Storage of graphs and networks
In this section, we'll learn about a few ways graph structures are commonly stored in computer memory and their benefits and drawbacks, including adjacency lists, adjacency matrices, and weight matrices.
Definition: adjacency list
For a graph G = (V, E), an adjacency list is an enumeration of the edges in a graph. In computer memory, we would store it as a list of pairs of vertex numbers.
Definition: adjacency matrix
For a graph G = (V, E), an adjacency matrix for a graph is a binary matrix A = (aij). If eij 
E, then the number in row i and column j is aij = 1. Otherwise, it is 0.
In other words, the value in the ith row and jth column of the adjacency matrix A, aij, is 1 if vertices vi and vj are adjacent. Otherwise, it is 0.
Example: an adjacency list and an adjacency matrix
For the graph G in Figure 8.1, we previously listed the edges as E = {e12, e13, e15, e23, e24, e26, e34, e35, e45}. The adjacency list will simply be a...
