Let G be a DAG with vertices labeled 1,2, Define the adjacency matrix and adjace

Question

Let G be a DAG with vertices labeled 1,2, Define the adjacency matrix and adjacency list representations of G as in Rosen, page 669. Let A be the adjacency matrix that represents G. Write pseudocode that takes A as an input and outputs the array InDegree [] for the graph G. Let A be the adjacency matrix that represents G. Write a high-level English description of an algorithm that takes as inputs A and a source vertex v and outputs the adjacency matrix that represents G - v. Let L be the adjacency list that represents G. Write pseudocode that takes L as an input and outputs the array InDegree [] for the graph G. Let L be the adjacency list that represents G. Write a high-level English description of an algorithm that takes as inputs L and a source vertex v and outputs the adjacency list that represents G - v.

Explanation / Answer

a)

int[] findInDegree( A )
{
   InDeg[V]//create an array of size = number of vertices
    for i=1 to V
       InDeg[i] = 0 // initialize each element of InDegree to 0
  
   for i=1 to V
       for j=1 to V
           if Aij == 1
               InDeg[j] = InDeg[j]+1 // if there is a edge from i to j , he increase the inDegree of j by 1

return InDeg

}

b)

1) create a matrix A' of size (v-1)X(v-1)
2) Copy all values of A to A' , except vth row and vth column

c)

int[] findInDegree(Adj[])
{
   InDeg[V]//create an array of size = number of vertices
    for i=1 to V
       InDeg[i] = 0 // initialize each element of InDegree to 0
  
   for i=1 to V
       for each v E Adj[i]
           InDeg[v] = InDeg[v]+1

retur InDeg

}

d)

1) create a list L' of size |V|-1
2) for each list l in L except L[v], copy them to L'
3) for each list l' in L', search if l contain v
4) if it contain v then remove it from l

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

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