1.
Introduction
2.
Approach
3.
Implementation
3.1.
C++ Code
3.2.
Java Code
3.3.
Python Code
4.
Time Complexity
5.
5.1.
What is a graph?
5.2.
What are the two important graph traversal techniques?
5.3.
What are the two different ways to represent a graph?
6.
Conclusion
Last Updated: Mar 27, 2024
Easy

# Transpose Graph

Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

## 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').

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

## 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
{
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<<endl;
}
}

// function to create a Transpose graph using the adjacency list
{
// 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++)
{
}

}
}

// function call to display the adjacency list of original graph G
cout<<"Original Graph"<<endl;

// function call to find the transpose Graph G' of Graph G

// function call to display the adjacency list of transpose graph G'
cout<<"Transpose Graph"<<endl;

}

int main()
{
int V = 5;

// A utill function is called that accepts an adjacency list

return 0;
}

### Java Code

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 + " : ");
// 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)) {
}
}
}

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++) {
}
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++) {
}

}
}

### Python Code

# to create an edge from u to v

# To print the adjacency list of graph
for u in range(V):
# Source vertex
print(u, " : ", end = "")
# destination vertex
print()

# function to create a Transpose graph using the adjacency list

# 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

# function call to display the adjacency list of original graph G
print("Original Graph")
# function call to find the transpose Graph G' of graph G
transposeGraphAdj = [[] for i in range(V)]
# function call to display the adjacency list of transpose graph G'
print("Transpose Graph")

# Driver Code
if __name__ == '__main__':

V = 5
originalGraphAdj = [[] for i in range(V)]

Output:

Original Graph
0  : 2 3
1  :
2  : 4
3  : 2
4  : 1
Transpose Graph
0  :
1  : 4
2  : 0 3
3  : 0
4  : 2

## Time Complexity

Time complexity: O(V+E), where V denotes the number of vertices of the graph and E denotes the number of edges of the graph.

Check out this problem - Reverse Nodes In K Group

### What is a graph?

A graph is a non-linear data structure made up of a finite number of nodes connected using edges.

### What are the two important graph traversal techniques?

BFS(Breadth First Search) and DFS(Depth First Search) are two important graph traversal techniques.

### What are the two different ways to represent a graph?

The adjacency matrix and adjacency list are two of the ways to represent a graph.