5 5 pts Write using pseudode a function reverseG to perform

5 (5 pts) Write (using pseudode) a function reverse(G) to perform for the following task: Input: A directed graph G = (V, E) Output: GR = (V, ER), the reverse graph of G, where ER = {(u, v)|(v, u) E} For each vertex v E, let A[v] be the list of neighbors of v. What is the run-time of the function? Justify your answer.

Solution

(assume that each edge e has a source vertex u and a sink vertex v associated with it.)

function reverse(G)
Input: Graph G = (V,E) in adjacency list representation
Output: Graph G^R = (V,E^R)
Generate all edges e E using any traversal
Construct adjacency list G^R:
vertex set = V
For each generated edge e
temp = e.source
e.source = e.sink
e.sink = temp
insert e into G^R
return G^R

run-time: All edges can be generated in O(V + E). Edges can be modified and new adjacency list can be populated in O(E). Therefore the algorithm is linear.