7 Determining the Degree of Each Vertex

If the graph $G=(V,E)$ is represented by its adjacency list $A(G)$ and vertex list $V(G)$, Algorithm 13 develops a mapping $\lambda$ whose domain is $V(G)$ and whose range is the degree of $V(G)$. It assumes the buffer $v$ provides communication with the vertex list.

Algorithm 13: Determine Vertex Degree Using Adjacency List
 $k=$first($V$) while $k\neq eol$ map($\lambda,v,0$) $k=$next($V,k$) $k=$first($V$) while $k\neq eol$ for all vertices $w$ adjacent to $v$ $n=$evaluate($\lambda,w$)$+1$ map($\lambda,v,n$) $k=$next($V,k$)

If $G$ is a directed graph, represented by its vertex list $V(G)$ and edge list $E(G)$, Algorithm 14 maps each vertex in $V(G)$ to its degree. It is assumed that each edge is represented by an ordered pair of vertices $(v,w)$ and the buffer $e$ provides communication with the edge list.

Algorithm 14: Determine Vertex Degree of Directed Graph Using Edges
 $k=$first($V$) while $k\neq eol$ map($\lambda,v,0$) $k=$next($V,k$) $k=$first($E$) while $k\neq eol$ $n=$evaluate($\lambda,e.v$)$+1$ map($\lambda,e.v,n$) $k=$next($E,k$)

If $G$ is an undirected graph, Algorithm 15 performs the same operation. It is assumed that each edge is represented by an unordered pair of vertices $(v,w)$.

Algorithm 15: Determine Vertex Degree of Undirected Graph Using Edges
 $k=$first($V$) while $k\neq eol$ map($\lambda,v,0$) $k=$next($V,k$) $k=$first($E$) while $k\neq eol$ $n=$evaluate($\lambda,e.v$)$+1$ map($\lambda,e.v,n$) $n=$evaluate($\lambda,e.w$)$+1$ map($\lambda,e.w,n$) $k=$next($E,k$)

If all the elementary operations are $O(1)$, creating $\lambda$ is linear, i.e. has complexity $O\left(|V|+|E|\right)$.