Text: 3. (15p). We again consider directed graphs, with nodes 1..n and with a ed
ID: 3209831 • Letter: T
Question
Text:
3. (15p). We again consider directed graphs, with nodes 1..n and with a edges (this time without weights). Our aim is now to reverse the graph; that is, from a given graph (V,E) we want to construct a graph (V,E) such that for all i and k in V, E contains an edge from i to k iff E contains an edge from k to i.
1. (10p) First assume the graph is represented as an adjacency matrix A, with the boolean A(i,k) true iff the graph has an edge from i to k. Write an algorithm to implement this specification, and analyze its running time, as a function of n and of a.
2. (5p) Next assume the graph is represented as adjacency lists L (that is, for each i 1..n, the list L[i] contains the targets of edges with source i). Then the specification can be implemented by the algorithm below (where Cons adds an edge to a list of edges) whose running time, as a function of n and of a, you must analyze.
for k 1 to n L[k] Empty
for i 1 to n foreach k L[i]
L[k] Cons(i, L[k])
3. (15p). We again consider directed graphs, with nodes 1..n and with a edges (this time without weights). Our aim is now to reverse the graph; that is, from a given graph (V, E) we want to construct a graph (V, E') such that for al i and k in V, E' contains an edge from i to k iff E contains an edge from k to i 1. (10p) First assume the graph is represented as an adjacency matrix A, with the boolean A(i, k) true iff the graph has an edge from i to k. Write an algorithm to implement this specification, and analyze its running time, as a function of n and of a 2. (5p) Next assume the graph is represented as adjacency lists L (that is, for each i E La the list Li] contains the targets of edges with source i). Then the specification can be implemented by the algorithm below (where CONS adds an edge to a list of edges) whose running time, as a function of n and of a, you must analyze. for k 1 to n ,[ EMPTY for i 1 to n foreach k E LExplanation / Answer
a) To reverse a graph represented as an adjacency matrix we just need to find the transpose of the matrix.
static void reverseGraph(int graph[][], int reverse[][]){
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
reverse[i][j] = graph[j][i];
}
if we assume it is a square matrix ,T(n)=(T(n-1)+n whih gives O(n^2).
else O(|V|*|E|)=O(n*m)
b)time complexity- of this algorithm can be analysed as T(n)=(T(n-1)+n which gives O(n^2) or O(|V|*|E|)=O(n*k)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.