4. (25 points) The reverse of a directed graph G is another directed graph GR with...

 

Transcribed Image Text:

4. (25 points) The reverse of a directed graph G is another directed graph GR with the same vertex set with the property that if (u, v) is an edge in G then (v, u) is an edge in GR. Consider the following algorithm that takes the adjacency list A[v1, v2, ..., Un] of a directed graph G as input and outputs an adjacency list of GR. procedure reversegraph (A[v1, v2,..., Un]) initialize a list AR [V1,..., Un] for each i 1...n: for each uA[vi]: add vi to the list A [u] return AR (a) Justify the correctness of this algorithm (b) Analyze the runtime of this algorithm assuming that G has n vertices and m edges. 4. (25 points) The reverse of a directed graph G is another directed graph GR with the same vertex set with the property that if (u, v) is an edge in G then (v, u) is an edge in GR. Consider the following algorithm that takes the adjacency list A[v1, v2, ..., Un] of a directed graph G as input and outputs an adjacency list of GR. procedure reversegraph (A[v1, v2,..., Un]) initialize a list AR [V1,..., Un] for each i 1...n: for each uA[vi]: add vi to the list A [u] return AR (a) Justify the correctness of this algorithm (b) Analyze the runtime of this algorithm assuming that G has n vertices and m edges.