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