# Transpose graph

Transpose of a directed graph G is another directed graph on the same set of vertices with all of the edges reversed compared to the orientation of the corresponding edges in G. That is, if G contains an edge (u, v) then the converse/transpose/reverse of G contains an edge (v, u) and vice versa.
Given a graph (represented as adjacency list), we need to find another graph which is the transpose of the given graph.

Example:

Transpose Graph

```Input : figure (i) is the input graph.
Output : figure (ii) is the transpose graph of the given graph.
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

We traverse the adjacency list and as we find a vertex v in the adjacency list of vertex u which indicates an edge from u to v in main graph, we just add an edge from v to u in the transpose graph i.e. add u in the adjacency list of vertex v of the new graph. Thus traversing lists of all vertices of main graph we can get the transpose graph. Thus the total time complexity of the algorithm is O(V+E) where V is number of vertices of graph and E is the number of edges of the graph.
Note : It is simple to get the transpose of a graph which is stored in adjacency matrix format, you just need to get the transpose of that matrix.

## C++

 `// CPP program to find transpose of a graph. ` `#include ` `using` `namespace` `std; ` ` `  `// function to add an edge from vertex source to vertex dest ` `void` `addEdge(vector<``int``> adj[], ``int` `src, ``int` `dest) ` `{ ` `    ``adj[src].push_back(dest);  ` `} ` ` `  `// function to print adjacency list of a graph ` `void` `displayGraph(vector<``int``> adj[], ``int` `v) ` `{ ` `    ``for` `(``int` `i = 0; i < v; i++) { ` `        ``cout << i << ``"--> "``; ` `        ``for` `(``int` `j = 0; j < adj[i].size(); j++) ` `            ``cout << adj[i][j] << ``"  "``; ` `        ``cout << ````" "````; ` `    ``} ` `} ` ` `  `// function to get Transpose of a graph taking adjacency ` `// list of given graph and that of Transpose graph ` `void` `transposeGraph(vector<``int``> adj[],  ` `                     ``vector<``int``> transpose[], ``int` `v) ` `{ ` `    ``// traverse the adjacency list of given graph and ` `    ``// for each edge (u, v) add an edge (v, u) in the ` `    ``// transpose graph's adjacency list ` `    ``for` `(``int` `i = 0; i < v; i++) ` `        ``for` `(``int` `j = 0; j < adj[i].size(); j++) ` `            ``addEdge(transpose, adj[i][j], i); ` `} ` ` `  `int` `main() ` `{ ` `    ``int` `v = 5; ` `    ``vector<``int``> adj[v]; ` `    ``addEdge(adj, 0, 1); ` `    ``addEdge(adj, 0, 4); ` `    ``addEdge(adj, 0, 3); ` `    ``addEdge(adj, 2, 0); ` `    ``addEdge(adj, 3, 2); ` `    ``addEdge(adj, 4, 1); ` `    ``addEdge(adj, 4, 3); ` ` `  `    ``// Finding transpose of graph represented ` `    ``// by adjacency list adj[] ` `    ``vector<``int``> transpose[v]; ` `    ``transposeGraph(adj, transpose, v); ` ` `  `    ``// displaying adjacency list of transpose  ` `    ``// graph i.e. b ` `    ``displayGraph(transpose, v); ` ` `  `    ``return` `0; ` `} `

## Python3

# Python3 program to find transpose of a graph.

# function to add an edge from vertex
# source to vertex dest

# of a graph
for i in range(v):
print(i, “–> “, end = “”)
print()

# function to get Transpose of a graph
# taking adjacency list of given graph
# and that of Transpose graph

# traverse the adjacency list of given
# graph and for each edge (u, v) add
# an edge (v, u) in the transpose graph’s
for i in range(v):

# Driver Code
if __name__ == ‘__main__’:

v = 5
adj = [[] for i in range(v)]

# Finding transpose of graph represented
transpose = [[]for i in range(v)]

# transpose graph i.e. b
displayGraph(transpose, v)

# This code is contributed by PranchalK

Output:

```0--> 2
1--> 0  4
2--> 3
3--> 0  4
4--> 0
```

## tags:

Graph graph-basics Graph