4 Creating Adjacency Lists

An undirected graph G=V,EG=(V,E) is represented by the sets VGV(G) and EGE(G). If these sets are maintained as simple lists where the buffer vv communicates with the vertex list and ee communicates with the edge list, Algorithm 1 creates an adjacency list AA for GG.

Algorithm 1: Create Adjacency List of Undirected Graph
i=i=first(VV)
while keolk\neq eol
    insert(A,v,headerA,v,header)
    k=k=next(V,kV,k)
k=k=first(EE)
while keolk\neq eol
    insert(A,e.v,e.wA,e.v,e.w)
    insert(A,e.w,e.vA,e.w,e.v)
    k=k=next(E,kE,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 EGE(G) into the adjacency list twice: once in the stated direction and once in the reverse direction. If GG 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 OV+EO\left(|V|+|E|\right) if all operators have time complexity of O1O(1).

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

Algorithm 2: Map Vertices To Labeling Order
i=0i=0
k=k=first(VV)
while keolk\neq eol
    i=i+1i=i+1
    map(μ,v,i\mu,v,i)
    k=k=next(V,kV,k)

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

Algorithm 3: Create Ordered Adjacency List
i=0i=0
k=k=first(VV)
while keolk\neq eol
    i=i+1i=i+1
    map(μ,v,i\mu,v,i)
    insert(A,v,headerA,v,header)
    k=k=next(V,kV,k)
kk = first(EE)
while keolk\neq eol
    i=i=evaluate(μ,e.v\mu,e.v)
    j=j=evaluate(μ,e.w\mu,e.w)
    insert(A,i,jA,i,j)
    insert(A,j,iA,j,i)
    k=k=next(E,kE,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(d,r) into a data structure that is optimized for searching and evaluate will look up dd in this data structure. Efficient operations of this sort have a time complexity of Olog2nO\left(\,\log _{2}n\,\right). Therefore, adjacency list creation will have complexity OVlog2V+Elog2VO\left(\,|V|\log _{2}|V|+|E|\log _{2}|V|\,\right).