114points Let G- (V,E) be a directed graph. The in-degree of a vertex v is the n
ID: 3717130 • Letter: 1
Question
114points 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 EV, computes the in-degree of v under (b) Design an algorithm (give pseudocode) that, given a vertex v E 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 algorithmExplanation / Answer
Ans a) If the graph is represented as adjacency list then we just have to count the lenght of the list.
// i have assumed that list is implemented as a linked list.
int count(List ls){
int count=0;
List temp = ls;
while(temp != NULL){
count++;
temp = temp->next;
}
return count++;
}
Ans b) If the graph is represented as adjacency matrix then we just have to count the lenght of the list.
int count(Graph G,Vertex v, int nVertices){
int count=0;
for(int i=0;i<nVertices;i++){
if(G[v][i] == 1){ // it checks if there is an edge between vertex v and i.
count++;
}
}
return count;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.