# Transpose Graph

Frequently asked in Accenture Amazon JP Morgan Microsoft Zycus
Basic Cyptography GraphViews 1865

## Problem Statement

The problem “Transpose graph” states that you are given a graph and you need to find the transpose of the given graph.

Transpose: Transpose of a directed graph produces another graph with same edge & node configurations but the direction of all the edges have been reversed.

## Example ## Types of Solution for finding transpose graph

#### Approach

Traverse adjacency list of each node of the graph. Say, the node is u, now traverse each node in the adjacency list of u. Say, the node is v (i.e. u -> v) . In the transpose graph, add u to adjacency list of v (there exists and edge from v to u i.e. v -> u). Repeat this process for all the nodes (& their respective adjacency lists) in the graph until the transposed graph has been obtained. #### Code

##### C++ Program to find Transpose graph
```#include <iostream>
#include <bits/stdc++.h>
using namespace std;

// Add Edge from node u to v
void addEdge(vector <int> graph[], int u, int v)
{
graph[u].push_back(v);
}

int main()
{
// Construct the Given graph
int n = 7;
vector <int> graph[n];
vector<pair<int,int>> edges = {{0,1},{0,2},{3,2},{3,4},{4,5},{6,5},{6,0}};

for(auto e : edges)

// Print Adjacency list of given Graph
cout<<"The Adjacency List of Given Graph "<<endl;
for(int i=0;i<n;i++)
{
cout<<i<<"->";
for(auto node : graph[i])
cout<<node<<" ";

cout<<endl;
}

// Obtain transpose of the given graph
vector <int> transpose[n];
for(int i=0;i<n;i++)
{
for(auto node : graph[i])
}

// Print Adjacency list of the Transpose
cout<<endl<<"The Adjacency List of Transpose Graph "<<endl;
for(int i=0;i<n;i++)
{
cout<<i<<"->";
for(auto node : transpose[i])
cout<<node<<" ";

cout<<endl;
}

return 0;
}```
```The Adjacency List of Given Graph
0->1 2
1->
2->
3->2 4
4->5
5->
6->5 0

The Adjacency List of Transpose Graph
0->6
1->0
2->0 3
3->
4->3
5->4 6
6->```
##### Java Program to find Transpose graph
```import java.util.*;
import java.io.*;

class TutorialCup
{
// Add Edge from node u to v
static void addEdge(ArrayList<ArrayList<Integer>> graph, int u, int v)
{
}

public static void main (String[] args)
{
// Construct the Given graph
int n = 7;
ArrayList<ArrayList<Integer>> graph = new ArrayList<>();

for(int i=0;i<n;i++)

int [][] edges = {{0,1},{0,2},{3,2},{3,4},{4,5},{6,5},{6,0}};

for(int i=0;i<edges.length;i++)

// Print Adjacency list of given Graph
System.out.println("The Adjacency List of Given Graph ");
for(int i=0;i<n;i++)
{
System.out.print(i+"->");

Iterator itr = graph.get(i).iterator();

while(itr.hasNext())
{
int node = (Integer)itr.next();
System.out.print(node+" ");
}

System.out.println();
}

// Obtain transpose of the given graph
ArrayList<ArrayList<Integer>> transpose = new ArrayList<>();

for(int i=0;i<n;i++)

for(int i=0;i<n;i++)
{
Iterator itr = graph.get(i).iterator();

while(itr.hasNext())
{
int node = (Integer)itr.next();
}
}

// Print Adjacency list of the Transpose
System.out.println("\nThe Adjacency List of Transpose Graph ");
for(int i=0;i<n;i++)
{
System.out.print(i+"->");

Iterator itr = transpose.get(i).iterator();

while(itr.hasNext())
{
int node = (Integer)itr.next();
System.out.print(node+" ");
}

System.out.println();
}

}
}```
```The Adjacency List of Given Graph
0->1 2
1->
2->
3->2 4
4->5
5->
6->5 0

The Adjacency List of Transpose Graph
0->6
1->0
2->0 3
3->
4->3
5->4 6
6->```

#### Complexity Analysis for transpose graph using adjacency list

1. Time Complexity: T(n) = O(V+E), iterative traversal of adjacency list. Because we have just traversed over all of the nodes in the graph.
2. Space Complexity: A(n) = O(V+E), because we need new adjacency list for storing the transpose graph.

V = number of vertices in the graph.

E = number of edges in the graph.

#### Approach

The transpose of the graph defined by n x n adjacency matrix (where n = number of nodes) is it’s matrix transpose.

Algorithm

1. Define the graph using adjacency matrix.
2. Perform transpose of the adjacency matrix to obtain transpose of the given graph. #### Code

##### C++ Program to find Transpose graph
```#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int main()
{
vector<vector<int>> graph = {{0,1,1,0,0,0,0},
{0,0,0,0,0,0,0},
{0,0,0,0,0,0,0},
{0,0,1,0,1,0,0},
{0,0,0,0,0,1,0},
{0,0,0,0,0,0,0},
{1,0,0,0,0,1,0}};

for(auto node : graph)
{
for(auto neighbor : node)
cout<<neighbor<<" ";

cout<<endl;
}

// Perform Matrix Transpose
for(int i=0;i<graph.size();i++)
{
for(int j=i+1;j<graph.size();j++)
swap(graph[i][j],graph[j][i]);
}

// Print the Matrix Transpose
for(auto node : graph)
{
for(auto neighbor : node)
cout<<neighbor<<" ";

cout<<endl;
}

return 0;
}```
```Adjacency Matrix of Given Graph.
0 1 1 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 1 0 1 0 0
0 0 0 0 0 1 0
0 0 0 0 0 0 0
1 0 0 0 0 1 0

0 0 0 0 0 0 1
1 0 0 0 0 0 0
1 0 0 1 0 0 0
0 0 0 0 0 0 0
0 0 0 1 0 0 0
0 0 0 0 1 0 1
0 0 0 0 0 0 0
```
##### Java Program to find Transpose graph
```import java.util.*;
import java.io.*;

class TutorialCup
{
public static void main (String[] args)
{
int [][] graph =            {{0,1,1,0,0,0,0},
{0,0,0,0,0,0,0},
{0,0,0,0,0,0,0},
{0,0,1,0,1,0,0},
{0,0,0,0,0,1,0},
{0,0,0,0,0,0,0},
{1,0,0,0,0,1,0}};

for(int i=0;i<graph.length;i++)
{
for(int j=0;j<graph.length;j++)
System.out.print(graph[i][j]+" ");

System.out.println();
}

// Perform Matrix Transpose
for(int i=0;i<graph.length;i++)
{
for(int j=i+1;j<graph.length;j++)
{
int temp = graph[i][j];
graph[i][j] = graph[j][i];
graph[j][i] = temp;
}
}

// Print the Matrix Transpose
for(int i=0;i<graph.length;i++)
{
for(int j=0;j<graph.length;j++)
System.out.print(graph[i][j]+" ");

System.out.println();
}
}
}```
```Adjacency Matrix of Given Graph.
0 1 1 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 1 0 1 0 0
0 0 0 0 0 1 0
0 0 0 0 0 0 0
1 0 0 0 0 1 0

0 0 0 0 0 0 1
1 0 0 0 0 0 0
1 0 0 1 0 0 0
0 0 0 0 0 0 0
0 0 0 1 0 0 0
0 0 0 0 1 0 1
0 0 0 0 0 0 0```

#### Complexity Analysis for transpose graph using adjacency matrix

1. Time Complexity: T(n) = O(V x V) Here also we have traversed through all nodes for each node in graph. Thus O(V*V), that is polynomial-time complexity.
2. Space Complexity: A(n) = O(1), no extra space used. Here we done an in-place task, we have replaced the values in the initial matrix. Thus constant space is taken.

V = number of vertices in the graph.

E = number of edges in the graph.

Translate »