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