12.2 AdjacencyLists: A Graph as a Collection of Lists

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 $ G=(V,E)$ is represented as an array, $ \ensuremath{\ensuremath{\mathit{adj}}}$, of lists. The list $ \ensuremath{\ensuremath{\mathit{adj}}[\ensuremath{\mathit{i}}]}$ contains a list of all the vertices adjacent to vertex $ \ensuremath{\ensuremath{\mathit{i}}}$. That is, it contains every index $ \ensuremath{\ensuremath{\mathit{j}}}$ such that $ \ensuremath{\ensuremath{(\ensuremath{\mathit{i}},\ensuremath{\mathit{j}})}}\in E$.
\begin{leftbar}
\begin{flushleft}
\hspace*{1em} \ensuremath{\mathrm{initialize}(...
...ets \ensuremath{\mathrm{\mathrm{ArrayStack}}()}}\\
\end{flushleft}\end{leftbar}
(An example is shown in Figure 12.3.) In this particular implementation, we represent each list in $ \ensuremath{\ensuremath{\mathit{adj}}}$ as ArrayStack, because we would like constant time access by position. Other options are also possible. Specifically, we could have implemented $ \ensuremath{\ensuremath{\mathit{adj}}}$ as a DLList.

Figure 12.3: A graph and its adjacency lists
\includegraphics[scale=0.90909]{figs-python/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 $ \ensuremath{\mathrm{add\_edge}(\ensuremath{\mathit{i}},\ensuremath{\mathit{j}})}$ operation just appends the value $ \ensuremath{\ensuremath{\mathit{j}}}$ to the list $ \ensuremath{\ensuremath{\mathit{adj}}[\ensuremath{\mathit{i}}]}$:
\begin{leftbar}
\begin{flushleft}
\hspace*{1em} \ensuremath{\mathrm{add\_edge}(\...
...t{i}}].\mathrm{append}(\ensuremath{\mathit{j}})}\\
\end{flushleft}\end{leftbar}
This takes constant time.

The $ \ensuremath{\mathrm{remove\_edge}(\ensuremath{\mathit{i}},\ensuremath{\mathit{j}})}$ operation searches through the list $ \ensuremath{\ensuremath{\mathit{adj}}[\ensuremath{\mathit{i}}]}$ until it finds $ \ensuremath{\ensuremath{\mathit{j}}}$ and then removes it:
\begin{leftbar}
\begin{flushleft}
\hspace*{1em} \ensuremath{\mathrm{remove\_edge...
...m} \hspace*{1em} {\color{black} \textbf{return}}\\
\end{flushleft}\end{leftbar}
This takes $ O(\deg(\ensuremath{\ensuremath{\ensuremath{\mathit{i}}}}))$ time, where $ \deg(\ensuremath{\ensuremath{\ensuremath{\mathit{i}}}})$ (the degree of $ \ensuremath{\ensuremath{\ensuremath{\mathit{i}}}}$) counts the number of edges in $ E$ that have $ \ensuremath{\ensuremath{\ensuremath{\mathit{i}}}}$ as their source.

The $ \ensuremath{\mathrm{has\_edge}(\ensuremath{\mathit{i}},\ensuremath{\mathit{j}})}$ operation is similar; it searches through the list $ \ensuremath{\ensuremath{\mathit{adj}}[\ensuremath{\mathit{i}}]}$ until it finds $ \ensuremath{\ensuremath{\mathit{j}}}$ (and returns true), or reaches the end of the list (and returns false):
\begin{leftbar}
\begin{flushleft}
\hspace*{1em} \ensuremath{\mathrm{has\_edge}(\...
...eturn}} \ensuremath{\ensuremath{\mathit{false}}}\\
\end{flushleft}\end{leftbar}
This also takes $ O(\deg(\ensuremath{\ensuremath{\ensuremath{\mathit{i}}}}))$ time.

The $ \ensuremath{\mathrm{out\_edges}(\ensuremath{\mathit{i}})}$ operation is very simple; it returns the list $ \ensuremath{\ensuremath{\mathit{adj}}[\ensuremath{\mathit{i}}]}$ :
\begin{leftbar}
\begin{flushleft}
\hspace*{1em} \ensuremath{\mathrm{out\_edges}(...
...suremath{\mathit{adj}}[\ensuremath{\mathit{i}}]}\\
\end{flushleft}\end{leftbar}

The $ \ensuremath{\mathrm{in\_edges}(\ensuremath{\mathit{i}})}$ operation is much more work. It scans over every vertex $ j$ checking if the edge $ \ensuremath{(\ensuremath{\mathit{i}},\ensuremath{\mathit{j}})}$ exists and, if so, adding $ \ensuremath{\ensuremath{\mathit{j}}}$ to the output list:
\begin{leftbar}
\begin{flushleft}
\hspace*{1em} \ensuremath{\mathrm{in\_edges}(\...
...{return}} \ensuremath{\ensuremath{\mathit{out}}}\\
\end{flushleft}\end{leftbar}
This operation is very slow. It scans the adjacency list of every vertex, so it takes $ O(\ensuremath{\ensuremath{\ensuremath{\mathit{n}}}} + \ensuremath{\ensuremath{\ensuremath{\mathit{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{\ensuremath{\ensuremath{\mathit{n}}}}+\ensuremath{\ensuremath{\ensuremath{\mathit{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:

Most of these questions come down to a tradeoff between complexity (and space) of implementation and performance features of the implementation.

opendatastructures.org