Question

22.1-1 Given an adjacency-list representation of a directed graph, how long does it take to compute the out-degree of every vertex? How long does it take to compute the in-degrees?

Answer 1

Let N be the number of vertices and E be the edges in given directed graph.

For finding out-degree of any vertex we can simply traverse over its adjacency list and count the number of vertices present there. Therefore, the total time taken to compute out-degree of every vertex would be O(N+E) with O(1) space.

For finding in-degree of any vertex, we need to count the number of occurrences of that vertex by traversing over the adjacency lists of all the vertices. This will take time O(N+E) for each vertex, i.e. overall time complexity is O(N*(N+E)) with constant space. We can improve this by taking a Count array of size N, initialized with zero. Then traverse over the adjacency lists of all vertices just once and increment the counter of the respective vertices present there. So total time taken is O(N+E) with O(N) space.

Please ask for clarifications if needed any and kindly give feedback!