Question

Consider an unweighted, undirected graph G = <V, E>. The neighbourhood of a node v ∈ V in the graph is the set of all nodes that are adjacent (or directly connected) to v. Subsequently, we can define the neighbourhood degree of the node v as the sum of the degrees of all its neighbours (those nodes that are directly connects to v).

(a) Design an algorithm that returns a list containing the neighbourhood degree for each node v ∈ V, assuming that the input is the graph, G, represented using an adjacency list. Each item i in the list that you generate will correspond to the correct value for the neighbourhood degree of node vi. Your algorithm should be presented in unambiguous pseudocode. Your algorithm should have a time complexity value O(V +E).

(b) If an adjacency matrix was used to represent the graph instead of an adjacency list, what is the new value for the time complexity? Justify your answer by explicitly referring to the changes that would be necessary to your algorithm from part (a).

Answer 1

SOLUTION

A)

function G)

//n is number of vertices or equal to V

deg [n]

//calculate degree of each vertex

for i=0 to i=n-1

deg [i] = len (adjacency_list [i])

neighbourhood_degree[n]

//for each vertex calculate it neighbourhood degree

for i=0 to n-1

//neighbourhood [i] is sum of degree of all vertices in adjacency_list of i

for j=0 to len (adjacency_list [i]-1)

neighbour_degree[i]+ = degree [adjacency_list [i] [j] ]

return neighbourhood_degree

The time complexity of algorithm is O (V+E)

B)

The time complexity of this part will be O(V²)

pseudo code

function neighbourhood_degree (G)

degree [n]

//calculate degree of each vertex

//in adjacency matrix one has to traverse each vertex and check if it has edge with that edge or not

//this operation take n²

for i=0 to n-1

for j=0 to n-1

if adjacency_matrix [i] [j] is non zero

degree [i]+=1

neighbourhood_degree [n]

//calculate neighbourhood_degree of each vertex

for i=0 to n-1

for j=0 to j=n-1

//if there is a edge between i and j

//add the degree [j] to neighbourhood of i

if adjacency_matrix [i] [j] is non zero

neighbourhood_degree [i]+=degree [j]

return neighbourhood_degree