Discrete Mathematics for Computer Science

Representation of Graphs 347

Since A(i, j) = A(j, i) for 1 < i, j < n, an adjacency matrix is symmetric. The diagonal

entries of an adjacency matrix are zero, since a graph has no edge with both ends the same.

Figure 6.18 shows a graph and its associated adjacency matrix.

123456789

1010001000 3010100000 9 2

3 0 1 0 1 0 0 0 0 0 ,2

4001010000 7

5000101000

6110010000 7000000010 6 3

8000000101

9 0 0 0 0 0 0 0 10 4

Figure 6.18 A graph and its adjacency matrix.

Other adjacency matrices for this graph can be formed by labeling the rows and

columns of the matrix differently. The number of paths joining any pair of vertices in a

graph can be found using an adjacency matrix. Exercise 43 in Section 6.6 will explore

some properties of adjacency matrices.

6.5.2 Adjacency Lists

An adjacency list representation of a graph G = (V, E) with n vertices only stores infor-

mation about the edges that are in a graph. An adjacency list representation for a graph

consists of a list of its vertices VI, V2 ..... v, together with a separate list for each vertex

that contains all the vertices adjacent to vi for 1 < i < n. Figure 6.19 shows the graph of

Figure 6.18 with an adjacency list representation.

List of

Vertices Adjacencies

1 26 6,.

2 1 6 3 8

3 4 2 3 4 5 7 2

5 4 6

6 1 5 2 6 3

7 8

(^8 79 5 4)
9 8
Figure 6.19 A graph and its adjacency list.
Other adjacency list representations can be constructed both by listing the vertices in a
different order and by listing the adjacencies of a vertex in a different order. An algorithm
that examines all the edges of a graph as a computation step can have different measures of
complexity if the graph is represented by an adjacency matrix rather than by an adjacency
list. Neither representation introduced, however, is always better than the other.