# Transpose Graph

Frequently asked in Accenture Amazon JP Morgan Microsoft Zycus
Basic Cyptography Graph

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

## 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[0].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[0].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[0].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[0].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.

Wait !!! You can Crack Technical Interviews of Companies like Amazon, Google, LinkedIn, Facebook, PayPal, Flipkart, etc

Anisha was able to crack Amazon after practicing questions from TutorialCup