Question

The reverse of a directed graph G = (V,E) is another directed graph${\mathbf{G}}^{\mathbf{R}}\mathbf{=}\mathbf{(}\mathbf{V}\mathbf{,}{\mathbf{E}}^{\mathbf{R}}\mathbf{)}$ on the same vertex set, but with all edges reversed that is,${\mathbf{E}}^{\mathbf{R}}\mathbf{=}\left\{(v,u):(u,v)\in E\right\}$ . Give a linear-time algorithm for computing the reverse of a graph in adjacency list format.

Short answer

A linear-time algorithm is used for reversal$G^{\mathit{R}}\mathit{=}\mathit{(}V\mathit{,}{E}^{\mathit{R}}\mathit{)}$ of a directed graph G=(V,E) by using an adjacency list is proved.

Step-by-step solution

Step 1: Adjacency List

The representation of the list contains an array known as an adjacency list.

An adjacency list consists of a linked list for each vertex.

The size of the array is the same as the number of vertices in it.

If the graph is an undirected graph, then each edge appears twice in the list.

Each list consists of the name of the vertex.

Reversing the adjacency lists of a Directed Graph can be done in linear time

Order of complexity will be O(V+E).

Reversal of graph takes linear time

Consider directed graph G =(V,E) which has vertices and edges. Firstly, perform the reversal of graph that is $G^R\mathit{=}\mathit{(}V\mathit{,}{E}^R\mathit{)}$. Let’s perform the reverse of the graph by changing the directions of edges that are connected to the vertex. After the reversal of the graph all the edges reversed that is, $\mathrm{E}=\left\{(\mathrm{v},\mathrm{u}):(\mathrm{u},\mathrm{v})\in \mathrm{E}\right\}$is shown in the figure below.

The degree of a node in a directed graph is the number of edges connected to the node. For each node in a graph there is a list. It will take a linear time in adjacency list and it always assign a degree value to each node. And while iterating from the list the total number of the vertex is the degree of the vertex. After reversal of the graph take the adjacency list and put all the vertices in the adjacency list one by one.

Draw the Reversal of the directed graph:

Adjacency list for directed graph is shown below:

As in this directed graph it contains five vertices so the size of the adjacency list here is five. After that as known that the graph is the directed graph so, the vertex connected by edges to the other vertex writes only those vertices in front of the list that take a temp as a variable for storing the temporary variable while traversing the directed graph to the adjacency list. Like here vertex one is connected by vertex two and vertex two is connected to vertex three like that mark in the adjacency list. Here each vertex has one linked list. After performing this step now, the graph contained the adjacency list. Where the time complexity is O (V+E) . Hence it is proved that this is a linear-time algorithm that takes O (V+E) time.

Prove by using example

Now take another example where a graph $\mathrm{G}=(\mathrm{V},\mathrm{E})$which have vertices and edges. Firstly, perform the reversal of graph that is $G^R\mathit{=}\mathit{(}V\mathit{,}{E}^R\mathit{)}$. Draw a directed graph for 5 vertices.

Let’s perform reverse of graph by changing the directions of edges that are connected to the vertex. After reversal of graph all the edges reversed that is$\mathrm{E}=\left\{(\mathrm{v},\mathrm{u}):(\mathrm{u},\mathrm{v})\in \mathrm{E}\right\}$,is shown in the figure below. Here five vertices and every edge are bidirectional so here in this example each vertex has a degree of two.

The indegree of each vertex is two and the outdegree of each vertex is also two. Now after performing the reversal of graph then put the vertices into the adjacency list. Where this list contain array named as adjacency list and it consists of a linked list for each vertex.

Here the reversing the adjacency lists of a Directed Graph can be done in linear time. And the order of complexity will be O (V+E).

Hence it is proved that a linear-time algorithm is used for computing the reversal of a graph by using adjacency list.