12.2 AdjacencyLists: A Graph as a Collection of Lists (original) (raw)

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 $ G=(V,E)$ is represented as an array, $ \mathtt{adj}$, of lists. The list $ \mathtt{adj[i]}$ contains a list of all the vertices adjacent to vertex $ \mathtt{i}$. That is, it contains every index $ \mathtt{j}$ such that $ \ensuremath{\mathtt{(i,j)}}\in E$.

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 $ \mathtt{adj}$ as an ArrayStack, because we would like constant time access by position. Other options are also possible. Specifically, we could have implemented $ \mathtt{adj}$ as a DLList.

**Figure 12.3:**A graph and its adjacency lists

\includegraphics{figs/graph} 0 1 2 3 4 5 6 7 8 9 10 11 1 0 1 2 0 1 5 6 4 8 9 10 4 2 3 7 5 2 2 3 9 5 6 7 6 6 8 6 7 11 10 11 5 9 10 4

The $ \mathtt{addEdge(i,j)}$ operation just appends the value $ \mathtt{j}$ to the list $ \mathtt{adj[i]}$:

void addEdge(int i, int j) {
    adj[i].add(j);
}

This takes constant time.

The $ \mathtt{removeEdge(i,j)}$ operation searches through the list $ \mathtt{adj[i]}$until it finds $ \mathtt{j}$ 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 $ O(\deg(\ensuremath{\mathtt{i}}))$ time, where $ \deg(\ensuremath{\mathtt{i}})$ (the degree of $ \ensuremath{\mathtt{i}}$) counts the number of edges in $ E$ that have $ \ensuremath{\mathtt{i}}$ as their source.

The $ \mathtt{hasEdge(i,j)}$ operation is similar; it searches through the list $ \mathtt{adj[i]}$ until it finds $ \mathtt{j}$ (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 $ O(\deg(\ensuremath{\mathtt{i}}))$ time.

The $ \mathtt{outEdges(i)}$ operation is very simple; It simply returns the list $ \mathtt{adj[i]}$:

List<Integer> outEdges(int i) {
    return adj[i];
}

This clearly takes constant time.

The $ \mathtt{inEdges(i)}$ operation is much more work. It scans over every vertex $ j$ checking if the edge $ \mathtt{(i,j)}$ exists and, if so, adding $ \mathtt{j}$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 $ O(\ensuremath{\mathtt{n}} + \ensuremath{\mathtt{m}})$ time.

The following theorem summarizes the performance of the above data structure:

Theorem 12..2 The AdjacencyLists data structure implements the Graph interface. An AdjacencyLists supports the operations

The space used by a AdjacencyLists is $ O(\ensuremath{\mathtt{n}} + \ensuremath{\mathtt{m}})$.

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