Let G = (V, E) be a directed graph, given in the adjacency list format. Define a directed graph G' = (V, E') where an edge (u, v) ∈ E' if and only if (v, u) ∈ E (namely, G'reverses the direction of each edge in G). Describe an algorithm to obtain an adjacency list representation of G' in O(|V | + |E|) time.
is there a simple way inverse the adjacency list?
say if it was:
a-> b
b-> de
c-> c
d-> ab
e->
to:
a-> d
b-> ad
c-> c
d-> ab
e-> b
Let's say you iterate the adjacency lists of all vertices in the graph as follows.
for each u in V:
for each v in adjacency_list[u]:
reverse_adjacency_list[v].append(u)
With this approach, you traverse the adjacency lists of all |V| vertices, which contributes O(|V|) to the overall time complexity of your algorithm. Also, as you traverse every item in the adjacency list, you effectively traverse all the edges in the graph. In other words, if you concatenated all the individual lists (i.e., adjacency_list[u]) you traverse as part of the adjacency list, the length of that resulting list would be |E|. Thus, another O(|E|) is contributed to the overall complexity.
Consequently, the time complexity will be O(|V| + |E|) with this pretty standard approach, and you do not need to devise any peculiar method to achieve this complexity.