[DS] Graph reversal

Question

What will be complexity to reverse the directed graph?(By reverse i mean reverse direction of all edges).Assume graph is represented by adjacency list.

i) No extra space

ii)May use extra space

Comments

You may check this:- https://stackoverflow.com/questions/16158926/how-to-reverse-a-graph-in-linear-time

Answer 1

$O(|V| + |E|)$

Consider this Directed Graph,

Now, adjacency list for this graph will be

V1 => V2

V2 => V3

V3 => V1

Create new empty list for all Nodes.

Key statement, 

V2 is present in V1's list means V1 to V2 we have directed edge. To make it reverse i.e. V2 to V1 directed edge, add V1 into V2's list(newly created list). follow this procedure for all nodes.

V2 => V3 means V2 to V3 we have directed edge so to reverse it, add V2 to V3's list(newly created list).

That's how we have reversed list in the end that is nothing but reversed directed edges.

New list for above graph will look like,

V1 => V3

V2 => V1

V3 => V2.

more explanation,

A => B | C | D is list that means we have directed edge from A to B, C, D. Now to make it reverse, add A to B, C and D's list(new list).

the list will look like,

B => A,

C => A, 

D => A.