DSA - Graphs and Hashing -Q15

Question

Consider the following statements about computing out-degree of every vertex in a Graph G: 

1. Given an adjacency-list representation of a directed graph G = (V, E), it takes time to compute the out-degree of every vertex without any additional storage. 

2. Given an adjacency-list representation of a directed graph G = (V , E), it takes time to compute the out-degree of every vertex with  additional storage.

Which of the above is correct? 

A. 1 Only 

B. 2 Only 

C. Both 1,2 

D. None 

Answer 1

Given an adjacency-list representation Adj of a directed graph, the outdegree of a vertex u is equal to the length of Adj[u], and the sum of the lengths of all the adjacency lists in Adj is |E|. Thus the time to compute the out-degree of one vertex v is (|Adj(v)|) and for all vertices is (V + E).