Representing Graphs

There are usually two standard ways to represent a graphG = (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 inV. For each vertexuinV, there's a list containing all verticesv so that there is an edge connectinguandvinE.Figure 6.3shows the adjacency list representation of the directed graph inFigure 6.1:

Figure 6.3: Adjacency list representation of the directed graph in Figure 6.1

For undirected graphs, we follow a similar strategy and build the adjacency list as if it were a directed graph with two edges between each pair of verticesuandv, which are(u, v)and(v, u).

Figure 6.4shows the adjacency list representation of the undirected graph inFigure 6.2:

Figure 6.4: Adjacency list representation...