14 points Let G-(V, E) be a directed graph. The in-degree of a vertex v is the n

Question

14 points Let G-(V, E) be a directed graph. The in-degree of a vertex v 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 V, computes the in-degree of u incident into v. the assumption that G is represented by an adjacency list. Give an analysis of your algorithm. (b) Design an algorithm (give pseudocode) that, given a vertex u under the assumption that G is represented by an adjacency matrix. Give an analysis of your algorithm

Explanation / Answer

a) Given adjacency matrix which contains VxV entries where 1 denots an edge from i to j, i is row number and j is column number

findInDegree(G, v):

1. Initialize variable indegree = 0

2. for i 0 to V:

            indegree = indegree + G[i][v]

3. return indegree

                       

Input: G which is matrix representation of graph ; v vertex for which compute indegree

Output: indegree of vertex v

Explanation: Iterate over column v and sum values in the column to get indegree of vertex v

Time Complexity: O(V)

b) Given adjacency list which is a collection of list in which there is a list associated with each vertex and eac such list shows the vertices to which current vertex is adjacent to.

findInDegree(G,v):

1. Initialize variable indegree = 0

2. for i 0 to V:

            head = G[i].head

            while(head != NULL):

                        if head -> data = vertex

                                    indegree++

                        head = head->next

3. return indegree

Input: G a collection of lists; v vertex for which indegree is to be computed

Output: indegree of vertex v

Explanation: Iterate over collection, in each list iterate till end and compare value stored in each node, if it's v then add 1 to indegree otherwise ignore

Time Complexity: O(V+E)

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.