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.

Answer 2

Both are O(m + n) where m is the number of edges and n is the number of vertices.

Start a set of counters, one for each vertex, one for in-degree and out for out-degree.

Scan the edges. For the out vertex of each edge, add one to the out-degree counter for that vertex. For the in vertex of each edge, add one to the in-degree counter for that vertex. This is O(m) operation.

Output the out-degree and in-degree counters for each vertex, which is O(n).

That's how you get O(m + n).

Answer 3

out-degree for every vertex:theta(E)

in-degree for each vertex:O(E)

E is the number of edges of the graph

Answer 4

Since, its a directed graph and only the adjacency list is given.

The time taken to count the number of out-degrees would be theta (M+N) where M is the number of vertices and N refers to number of edges.

Whereas for the count of number of in-degrees, for any node you have to count the number of occurrences of that node in all other(rest of vertices) adjacency list. So, it would take theta(MN).

However, if you maintain an Array of size M, then you can do the counting of the in-degree in theta(M+N) with an additional space storage of theta(M)

Answer 5

Computing both the in-degree and out-degree takes theta(m + n) for a graph with m vertices and n edges. The reason that it is theta(m+n) and not O(m + n) because whatever may be the graph , it has to go through every vertex m and every edge n.

Answer 6

Given an adjacency-list representation Adj of a directed graph, the out-degree 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 every vertex is Θ(|V| + |E|).

The in-degree of a vertex u is equal to the number of times it appears in all the lists in Adj. If we search all the lists for each vertex, the time to compute the in-degree of every vertex is Θ(|V|.|E|).

(Alternatively, we can allocate an array T of size |V| and initialize its entries to zero. Then we only need to scan the lists in Adj once, incrementing T[u] when we see u in the lists. The values in T will be the in-degrees of every vertex. This can be done in Θ(|V| + |E|) time with Θ(|V|) additional storage.)