2.3 Representing Sparse Graphs as Adjaceny Lists

An adjacency list is a data structure for representing adjacency relationships in sparse graphs. The adjacency list of GG is actually a set of V|V| linked lists. Each vertex vv is the head of a list. Vertices adjacent to vv form the body of each list. If a vertex is not adjacent to any other vertices its list is empty.

The storage required to implement an adjacency list is proportional to V+E|V|+|E|. When GG is represented as an adjacency list, the best time complexity you can expect for graph algorithms is OV+EO\left(|V|+|E|\right). The time required to access each vertex and each edge exactly one time. An algorithm whose time complexity is OV+EO\left(|V|+|E|\right) is sometimes referred to as linear in the size of GG.

Figure 7 depicts the adjacency list for the directed graph in Figure 1.

Figure 7: Adjacency List of Directed Graph in Figure 1

Figure 8 depicts the adjacency list for the undirected graph in Figure 2.

Figure 8: Adjacency List of Undirected Graph in Figure 2