Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Approach 
3.
Implementation
3.1.
C++ Code
3.2.
Java Code
3.3.
Python Code
4.
Time Complexity
5.
Frequently Asked Questions
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.

Transpose graph

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

Example of transpose graph

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
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;
}

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

Python Code

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


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

Frequently Asked Questions

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.

Conclusion

In this article, we have extensively discussed the Transpose Graph Problem.

After reading about this problem, are you not feeling excited to read/explore more articles on Graph? Don't worry; Coding Ninjas has you covered. To learn about the different types of graphs and applications, what is the difference between a graph and a tree, and what is breadth-first search

Recommended Readings:

If you wish to enhance your skills in Data Structures and AlgorithmsCompetitive ProgrammingJavaScript, 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. 

Do upvote if you find the blogs helpful.

Happy Learning!

Thank you
Previous article
Number of Connected Components in an Undirected Graph
Next article
Count single node isolated sub-graphs in a disconnected graph
Live masterclass