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.

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