Let G be a DAG with vertices labeled 1,2, Define the adjacency matrix and adjace
ID: 3668480 • Letter: L
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
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.