Question

For a directed graph the in-degree of a vertex is the number of edges it has coming in to it, and the out- degree is the number of edges it has coming out. (a) Let G[i,j] be the adjacency matrix representation of a directed graph, write pseudocode (in the same detail as the text book) to compute the in-degree and out-degree of every vertex in the Page 1 of 2 CSC 375 Homework 3 Spring 2020 directed graph. Store results in dictionaries in[] and out[] so that for a vertex v, in [v] and out[v] stores v's in and out degrees. (5 points) (b) Describe the running time of your algorithm assuming the directed graph has n vertices. (5 points)

Answer 1

Dear Student,

Let G is a directed Graph with v vertices and e edges.

a) Pseudocode for computing in-degrees and out-degrees.

/**********************code start here ************************/

degree( G[][], int v)

int in[v] , out[v]

// initialize every index of in[] and out[] with 0

for i <-- 0 to e:

for j <-- 0 to e:

if G[i][j] equals 1:

in[i] = in[i] + 1

out[j] = out[j] + 1

// end of if

// end of for

// end of for

//end of degree

b) Calculating time complexity of above algorithm if graph has n vertices.

degree( G[][], int v) // O(1)

int in[v] , out[v] //O(1)

// initialize every index of in[] and out[] with 0

for i <-- 0 to e: //O(n)

for j <-- 0 to e: // O(n)

if G[i][j] equals 1: // O(1)

in[i] = in[i] + 1 // O(1)

out[j] = out[j] + 1 // O(1)

// end of if

// end of for

// end of for

//end of degree

Total Time complexity = 1 + 1 + n*n(1 +1 +1)   // n*n because, for every iteration in first loop, second loop is running n times

=
2 + 3n

= O($n^2$) [ as $n^2$ is the biggest term in the above equation]