Do you think IIT Guwahati certified course can help you in your career?
Introduction
In this blog, we will look at the Transpose Graph problem in which we are given a directed graph with a set of vertices in the form of an adjacency list. The task is to find another directed graph G on the same set of vertices such that all the edges are reversed.
Approach
As mentioned in the problem statement, we are given a directed graph G that has a set of vertices, our task is to find another directed graph G' that has the same set of vertices but with all of the edges reversed. Basically, the transpose of a directed graph is another directed graph which has the same set of vertices as the original graph but has all of the edges reversed as compared to the original graph. Suppose there is an edge (u,v) that is from u to v in graph G, then in the transpose graph G', there will be an edge (v,u) that is from v to u.
In order to form the transpose graph G', we traverse through the original graph G, using its adjacency list. While traversing, if we find a vertex, say v, in the adjacency list of the vertex, say u, which means that there is an edge from vertex u to vertex v in the original graph G, then we simply add an edge from vertex v to vertex u in the transpose graph G' ( in the adjacency list of G').
Implementation
The implementation of the above algorithm in various programming languages is mentioned below:
C++ Code
#include <bits/stdc++.h>
using namespace std;
// To print the adjacency list of graph
void printGraphListForm(vector<int> adj[], int V)
{
for (int u = 0; u < V; u++)
{
// the source vertex
cout<<u<<" : ";
for (int v = 0; v < adj[u].size(); v++)
{
// the destination vertex
cout<<adj[u][v]<<" ";
}
cout<<endl;
}
}
// function to create a Transpose graph using the adjacency list
void getTranspose(vector<int> originalGraphAdj[],
vector<int> transposeGraphAdj[], int V)
{
// for every edge u->v in G,
// create an edge v->u in G'
for (int u = 0; u < V; u++)
{
// traverse the neighbours of each vertex
for (int x = 0; x < originalGraphAdj[u].size(); x++)
{
int v = originalGraphAdj[u][x];
transposeGraphAdj[v].push_back(u);
}
}
}
void utill(vector<int> originalGraphAdj[], int V){
// function call to display the adjacency list of original graph G
cout<<"Original Graph"<<endl;
printGraphListForm(originalGraphAdj, V);
// function call to find the transpose Graph G' of Graph G
vector<int> transposeGraphAdj[V];
getTranspose(originalGraphAdj, transposeGraphAdj, V);
// function call to display the adjacency list of transpose graph G'
cout<<"Transpose Graph"<<endl;
printGraphListForm(transposeGraphAdj, V);
}
int main()
{
int V = 5;
vector<int> originalGraphAdj[V];
originalGraphAdj[0].push_back(2);
originalGraphAdj[0].push_back(3);
originalGraphAdj[2].push_back(4);
originalGraphAdj[3].push_back(2);
originalGraphAdj[4].push_back(1);
// A utill function is called that accepts an adjacency list
utill(originalGraphAdj, V);
return 0;
}
You can also try this code with Online C++ Compiler
import java.util.*;
class Solution
{
// to print the adjacency list of graph
public static void printGraphListForm(int V, ArrayList<ArrayList<Integer>> adj)
{
for(int u = 0; u < V; u++){
// source vertex
System.out.print( u + " : ");
for(Integer v: adj.get(u)) {
// the destination vertex
System.out.print( v + " ");
}
System.out.println();
}
}
// function to create a transpose graph using the adjacency list
public static void getTranspose(ArrayList<ArrayList<Integer>> originalGraph, ArrayList<ArrayList<Integer>> transposeGraph, int V)
{
// for every edge u->v i G
// create an edge v->u in G'
for(int u = 0; u < V; u++){
// traverse the neighbours of each vertex
for(Integer v: originalGraph.get(u)) {
transposeGraph.get(v).add(u);
}
}
}
public static void utill(int V, ArrayList<ArrayList<Integer>> originalGraph)
{
// display the adjacency list of original graph G
System.out.println("Original Graph");
printGraphListForm(V, originalGraph);
// function call to find the transpose graph G' of graph G
ArrayList < ArrayList < Integer >> transposeGraph = new ArrayList < > ();
for (int i = 0; i < V; i++) {
transposeGraph.add(new ArrayList < > ());
}
getTranspose(originalGraph, transposeGraph, V);
// display the adjacency list of transpose graph G'
System.out.println("Transpose Graph");
printGraphListForm(V, transposeGraph);
}
public static void main(String args[]) {
ArrayList < ArrayList < Integer >> originalGraphAdj = new ArrayList < > ();
for (int i = 0; i < 5; i++) {
originalGraphAdj.add(new ArrayList < > ());
}
originalGraphAdj.get(0).add(2);
originalGraphAdj.get(0).add(3);
originalGraphAdj.get(2).add(4);
originalGraphAdj.get(3).add(2);
originalGraphAdj.get(4).add(1);
utill(5, originalGraphAdj);
}
}
You can also try this code with Online Java Compiler
# to create an edge from u to v
def addEdge(adj, u, v):
adj[u].append(v)
# To print the adjacency list of graph
def printGraphListForm(adj, V):
for u in range(V):
# Source vertex
print(u, " : ", end = "")
for v in range(len(adj[u])):
# destination vertex
print(adj[u][v], end = " ")
print()
# function to create a Transpose graph using the adjacency list
def getTranspose(originalGraphAdj, transposeGraphAdj, V):
# for every edge u->v in G,
# create an edge v->u in G'
for i in range(V):
# traverse the neighbours of each vertex
for x in range(len(originalGraphAdj[i])):
v = originalGraphAdj[i][x]
transposeGraphAdj[v].append(i)
def util(originalGraphAdj, V):
# function call to display the adjacency list of original graph G
print("Original Graph")
printGraphListForm(originalGraphAdj, V)
# function call to find the transpose Graph G' of graph G
transposeGraphAdj = [[] for i in range(V)]
getTranspose(originalGraphAdj, transposeGraphAdj, V)
# function call to display the adjacency list of transpose graph G'
print("Transpose Graph")
printGraphListForm(transposeGraphAdj, V)
# Driver Code
if __name__ == '__main__':
V = 5
originalGraphAdj = [[] for i in range(V)]
originalGraphAdj[0].append(2)
originalGraphAdj[0].append(3)
originalGraphAdj[2].append(4)
originalGraphAdj[3].append(2)
originalGraphAdj[4].append(1)
util(originalGraphAdj, V)
You can also try this code with Online Python Compiler
If you wish to enhance your skills in Data Structures and Algorithms, Competitive Programming, JavaScript, etc., you should check out our Guided path column at Code studio. We at Coding Ninjas Studio organize many contests in which you can participate. You can also prepare for the contests and test your coding skills by giving the mock test series available. In case you have just started the learning process, and your dream is to crack major tech giants like Amazon, Microsoft, etc., then you should check out the most frequently asked problems and the interview experiences of your seniors that will surely help you in landing a job in your dream company.
518+ registered 
