Adjacency list representations of graphs take a more vertex-centric
approach. There are many possible implementations of adjacency lists.
In this section, we present a simple one. At the end of the section,
we discuss different possibilities. In an adjacency list representation,
the graph is represented as an array,
, of lists. The list
contains a list of all the vertices adjacent to vertex
That is, it contains every index
(An example is shown in Figure 12.3.) In this particular implementation, we represent each list in as ArrayStack, because we would like constant time access by position. Other options are also possible. Specifically, we could have implemented as a DLList.
operation just appends the value
to the list
This takes constant time.
operation searches through the list
until it finds
and then removes it:
This takes time, where (the degree of ) counts the number of edges in that have as their source.
operation is similar; it searches through the list
until it finds
(and returns true), or reaches the end of
the list (and returns false):
This also takes time.
operation is very simple;
it returns the list
operation is much more work. It scans over every
vertex checking if the edge
exists and, if so, adding
to the output list:
This operation is very slow. It scans the adjacency list of every vertex, so it takes time.
The following theorem summarizes the performance of the above data structure:
As alluded to earlier, there are many different choices to be made when implementing a graph as an adjacency list. Some questions that come up include: