adjacency-list representation of a directed graph

Question

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?

Thanks

Answer 1

Adjacency-list representation of a directed graph:

Out-degree of each vertex

1. Graph out-degree of a vertex u is equal to the length of Adj[u].

2. The sum of the lengths of all the adjacency lists in Adj is |E|.

3. Thus the time to compute the out-degree of every vertex is Θ(V + E)

In-degree of each vertex

1. The in-degree of a vertex u is equal to the number of times it appears in all the lists in Adj.

2. If we search all the lists for each vertex, time to compute the in-degree of every vertex is Θ(VE)

3. Alternatively, we can allocate an array T of size |V| and initialize its entries to zero.

4. We only need to scan the lists in Adj once, incrementing T[u] when we see 'u' in the lists.

5. The values in T will be the in-degrees of every vertex.

6. This can be done in Θ(V + E) time with Θ(V) additional storage.