441 views
2 votes
2 votes
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

1 Answer

1 votes
1 votes

$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.

Related questions

4 votes
4 votes
1 answer
4
ramakrushna asked Dec 31, 2021
1,335 views
The number of insertion sequences of the numbers {1,2,3,4,5,6,7} which would lead to the following BSTHow to tackle this kind of problem. Anyone!