4 Creating Adjacency Lists

An undirected graph $G=(V,E)$ is represented by the sets $V(G)$ and $E(G)$. If these sets are maintained as simple lists where the buffer $v$ communicates with the vertex list and $e$ communicates with the edge list, Algorithm 1 creates an adjacency list $A$ for $G$.

The first loop in Algorithm 1 creates a header for each vertex. This operation is not strictly necessary given the current data definition; however, it is often required in practical implementations.

You should observe that the algorithm inserts each edge in $E(G)$ into the adjacency list twice: once in the stated direction and once in the reverse direction. If $G$ is a directed graph, the reverse insertion is inappropriate (i.e. omit the final insert statement in Algorithm 1). It should be apparent that the algorithm has a time complexity of $O\left(|V|+|E|\right)$ if all operators have time complexity of $O(1)$.

It is often beneficial to create an adjacency list based on an alternate labeling of the vertices of $G$. This operation requires a mapping $\mu$ of the integers from 1 to $|V|$ onto the set $V(G)$. Algorithm 2 maps $V(G)$ to the order in which it is enumerated.

Algorithm 3 combines these two procedures. It labels $V(G)$ according to its order of enumeration and creates an adjacency list based on this labeling.

If map and evaluate have constant time complexity, the overall algorithm retains its linear complexity.

Note. In a practical implementation, map will insert the pair $(d,r)$ into a data structure that is optimized for searching and evaluate will look up $d$ in this data structure. Efficient operations of this sort have a time complexity of $O\left(\,\log _{2}n\,\right)$. Therefore, adjacency list creation will have complexity $O\left(\,|V|\log _{2}|V|+|E|\log _{2}|V|\,\right)$.