Reverse a directed graph

Problem Statement:

You are given an directed graph.
You need to reverse the direction of the graph.

Example

Solution

We will take another graph to hold the reverse of a graph.

If there is a edge from v to u, then we add and edge from u to v in the reverse graph.

Solution in C++

#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <queue>
#include <vector>
#include <stack> 
#include <list> 

using namespace std;

class Graph
{

private:
   int V; 
   list<int> *adj; // to hold adjacency list
public:
   Graph(int V); // Constructor
   void add_edge(int v, int w); // to add an edge to graph
   void print_graph();
   Graph* reverse_graph();
};

Graph::Graph(int V)
{
   // get the total number of nodes
   this->V = V;

   // initialize adjacency list for that number of nodes
   adj = new list<int>[V];
}

void Graph::add_edge(int v, int w)
{
   // add the edge to adjacency list
   adj[v].push_back(w); 
}

void Graph::print_graph()
{
   for(auto i = 0; i < V; i++)
   {
      cout<<"\nAdjacency list of vertex "<<i<<endl;

      for(auto j = adj[i].begin(); j != adj[i].end(); j++)
      {
         cout<<" ->"<<*j;
      }
   }
}

Graph* Graph::reverse_graph()
{
   Graph *rev_graph = new Graph(V);

   for(int i = 0; i < V; i++)
   {
      for(auto j = adj[i].begin(); j != adj[i].end(); j++)
      {
         rev_graph->adj[*j].push_back(i);
      }
   }
   return rev_graph;
}

int main()
{

   Graph g(4);
   g.add_edge(0, 1);
   g.add_edge(1, 2);
   g.add_edge(2, 3);

   g.print_graph();

   cout<<"\nReverse of the graph"<<endl;

   Graph *reverse = g.reverse_graph();

   reverse->print_graph();

   return 0;
}

Output:

Adjacency list of vertex 0
 ->1
Adjacency list of vertex 1
 ->2
Adjacency list of vertex 2
 ->3
Adjacency list of vertex 3

Reverse of the graph

Adjacency list of vertex 0

Adjacency list of vertex 1
 ->0
Adjacency list of vertex 2
 ->1
Adjacency list of vertex 3
 ->