We have seen that the adjacency matrix can be used to represent a graph. However, this method proves to be rather inefficient when there are many 0's (that is, few edges) present. A better method uses the adjacency list representation, which is made up of an adjacency list for each vertex v and an index list. For the graph shown in Fig. 7.27, the representation is given by the two lists in Table 7.5.

For each vertex v in the graph, we list, preferably in numerical order, each vertex w that is adjacent from v. Hence for 1, we list 1, 2, 3 as the first three adjacencies in our adjacency list. Next to 2 in the index list we place a 4, which tells us where to start looking in the adjacency list for the adjacencies from 2. Since there is a 5 to the right of 3 in the index list, we know that the only adjacency from 2 is 6. Likewise, the 7 to the right of 4 in the index list directs us to the seventh entry in the adjacency list - namely, 3 -and we find that vertex 4 is adjacent to vertices 3 (the seventh vertex in the adjacency list) and 5 (the eighth vertex in the adjacency list). We stop at vertex 5 because of the 9 to the right of vertex 5 in the index list. The 9's in the index list next to 5 and 6 indicate that no vertex is adjacent from vertex 5. In a similar way, the 11's next to 7 and 8 in the index list tell us that vertex 7 is not adjacent to any vertex in the given directed graph.
In general, this method provides an easy way to determine the vertices adjacent from a vertex v. They are listed in the positions index(v), index(v) + 1, .. . , index(v + 1) - 1 of the adjacency list.
Finally, the last pair of entries in the index list - namely, 8 and 11 - is a "phantom" that indicates where the adjacency list would pick up from if there were an eighth vertex in the graph.
Represent each of the graphs in Fig. 7.28 in this manner.

Transcribed Image Text:

4 Figure 7.27 Table 7.5 Adjacency Lis Index List 4 4 7 3711 107 4 4 Figure 7.28