Representing Graphs

There are usually two standard ways to represent a graph G = (V, E) in a computer program:

• As a collection of adjacency lists
• As an adjacency matrix

You can use either way to represent both directed and undirected graphs. We'll start by looking at the adjacency list representation.

Adjacency List Representation

The adjacency list representation of a graph consists of an array of |V| lists, one for each vertex in V. For each vertex u in V, there's a list containing all vertices v so that there is an edge connecting u and v in E. Figure 6.3 shows the adjacency list representation of the directed graph in Figure 6.1:

Figure 6.3: Adjacency list representation of the directed...