Search⌘ K
AI Features
Home
Courses
Algorithms for Coding Interviews in C++

Solution: Print the Transpose of a Graph

Explore how to create the transpose of a graph by reversing all edges in its adjacency list. Understand the traversal process involved and analyze the solution's O(V+E) time complexity to efficiently implement graph transposition in C++.

We'll cover the following...

Solution: Traversal of Adjacency List

C++
#include<iostream> 
#include <list> 
#include <vector>
using namespace std; 
class Graph { 
	int vertices;
	list<int> *adjacencyList; 
  public:
    Graph();
    Graph(int V);
    void addEdge(int v, int w);
    void getTranspose();
    void printGraph();
};

This solution is pretty straight forward. Just make another graph, but start reversing it. Traverse the adjacency list of the given graph and—on encountering a vertex vv in the adjacency list of vertex uu ...