Table of Contents
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
Adjacency List
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)
addEdge(graph,e.first,e.second);
// 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])
addEdge(transpose,node,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)
{
graph.get(u).add(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++)
graph.add(new ArrayList<Integer>());
int [][] edges = {{0,1},{0,2},{3,2},{3,4},{4,5},{6,5},{6,0}};
for(int i=0;i<edges.length;i++)
addEdge(graph,edges[i][0],edges[i][1]);
// 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++)
transpose.add(new ArrayList<Integer>());
for(int i=0;i<n;i++)
{
Iterator itr = graph.get(i).iterator();
while(itr.hasNext())
{
int node = (Integer)itr.next();
addEdge(transpose,node,i);
}
}
// 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
- 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.
- 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.
Adjacency Matrix
Approach
The transpose of the graph defined by n x n adjacency matrix (where n = number of nodes) is it’s matrix transpose.
Algorithm
- Define the graph using adjacency matrix.
- 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()
{
// Define The Adjacency Matrix
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}};
cout<<"Adjacency Matrix of Given Graph."<<endl;
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
cout<<"\nAdjacency Matrix of Transpose Graph."<<endl;
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 Adjacency Matrix of Transpose Graph. 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)
{
// Define The Adjacency Matrix
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}};
System.out.println("Adjacency Matrix of Given Graph.");
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
System.out.println("\nAdjacency Matrix of Transpose Graph.");
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 Adjacency Matrix of Transpose Graph. 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
- 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.
- 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.