Let G be a DAG with vertices labeled 1, 2, . . . ,n. Define the adjacency matrix
ID: 3667072 • Letter: L
Question
Let G be a DAG with vertices labeled 1, 2, . . . ,n. 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) pseudocode ingreeofgraph(adjmatrix[ ][ ], n)
indegree[ ]={0}
For i=1 to i<=n do
for j=1 to n do
if adjmatrix[i][j]=1
indegree[j]+=1
end loop j
end loop i
for k=1 to n
print indegree[i]
b) A- adjacancy matrix
v- source vertex.
to print G-v:
From the given adjacancy matrix we need to remove row corresponding to v column corresponding to v.
c) adjacancy list L as input:
for *list=NULL
if list->next!=NULL //
length++
indegree[i]= length-1
end i loop
d) L is an adjacency list and source vertex v.
to construct adjacacency list we need to remove the vertex and also all the nodes in the list that contains that vertex.
i.e remove all incoming edges to vertex v
and remove all outgoing edges from vertex v.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.