Adjacency list representations takes a more vertex-centric approach. There are many different 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 such that .
int n; List<Integer>[] adj; AdjacencyLists(int n0) { n = n0; adj = (List<Integer>[])new List[n]; for (int i = 0; i < n; i++) adj[i] = new ArrayStack<Integer>(Integer.class); }(An example is shown in Figure 12.3.) In this particular implementation, we represent each list in as an ArrayStack, because we would like constant time access by position. Other options are also possible. Specifically, we could have implemented as a DLList.
|
The operation just appends the value to the list :
void addEdge(int i, int j) { adj[i].add(j); }This takes constant time.
The operation searches through the list until it finds and then removes it:
void removeEdge(int i, int j) { Iterator<Integer> it = adj[i].iterator(); while (it.hasNext()) { if (it.next() == j) { it.remove(); return; } } }This takes time, where (the degree of ) counts the number of edges in that have as their source.
The operation is similar; it searches through the list until it finds (and returns true), or reaches the end of the list (and returns false):
boolean hasEdge(int i, int j) { return adj[i].contains(j); }This also takes time.
The operation is very simple; It simply returns the list :
List<Integer> outEdges(int i) { return adj[i]; }This clearly takes constant time.
The operation is much more work. It scans over every vertex checking if the edge exists and, if so, adding to the output list:
List<Integer> inEdges(int i) { List<Integer> edges = new ArrayStack<Integer>(Integer.class); for (int j = 0; j < n; j++) if (adj[j].contains(i)) edges.add(j); return edges; }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:
opendatastructures.org