11. | 14 points! Let G = (V,E) be a directed graph. The in-degree of a vertex u
ID: 3282770 • Letter: 1
Question
11. | 14 points! Let G = (V,E) be a directed graph. The in-degree of a vertex u is the number of edges (a) Design an algorithm (give pseudocode) that, given a vertex v E V, computes the in-degree of v under (b) Design an algorithm (give pseudocode) that, given a vertex v ? V, computes the in-degree of v incident into v., the assumption that G is represented by an adjacency list. Give an analysis of your algorithm. under the assumption that G is represented by an adjacency matrix. Give an analysis of your algorithm.Explanation / Answer
a) Algorithm to find indegree represented by adjacency list
Algorithm for in-degree:
1 For each u in V do
2 in-deg[u] = 0
3 For each u in V do
4 For each v in Adj[u] do
5 in-deg[v] = in-deg[v] + 1 // count # of edges to v
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 all vertices 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.
b)
If A(G) is the n×n adjacency matrix of a digraph G,
and xj and xi are vertices such that xj,xi?V(G),
then
?nk=1akj=a1j+a2j+...+anj=deg?(xj)
(the sum of all entries in column j is equal to the in-degree of vertex xj) .
The adjacency-matrix A of any graph has ?(V 2 ) entries, regardless of the number of edges in the graph. For a directed graph, computing the out-degree of a vertex u is equivalent to scanning the row corresponding to u in A and summing the ones, so that computing the out-degree of every vertex is equivalent to scanning all entries of A. Thus the time required is ?(V ) for one vertex, and ?(V 2 ) for all vertices. Similarly, computing the in-degree of a vertex u is equivalent to scanning the column corresponding to u in A and summing the ones, thus the time required is also ?(V ) for one vertex, and ?(V 2 ) for all vertices.
Feel free to reach out regarding any queries . And please do rate the answer . Thank you .
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.