# 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$.

$i=$first($V$) |

while $k\neq eol$ |

insert($A,v,header$) |

$k=$next($V,k$) |

$k=$first($E$) |

while $k\neq eol$ |

insert($A,e.v,e.w$) |

insert($A,e.w,e.v$) |

$k=$next($E,k$) |

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.

$i=0$ |

$k=$first($V$) |

while $k\neq eol$ |

$i=i+1$ |

map($\mu,v,i$) |

$k=$next($V,k$) |

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.

$i=0$ |

$k=$first($V$) |

while $k\neq eol$ |

$i=i+1$ |

map($\mu,v,i$) |

insert($A,v,header$) |

$k=$next($V,k$) |

$k$ = first($E$) |

while $k\neq eol$ |

$i=$evaluate($\mu,e.v$) |

$j=$evaluate($\mu,e.w$) |

insert($A,i,j$) |

insert($A,j,i$) |

$k=$next($E,k$) |

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)$.