This post is completed by 1 user

  • 0
Add to List
Beginner

400. Reverse the Directed Graph

Objective: Given a directed graph, write an algorithm to reverse the graph. 

Example: 

Approach:

Create a new graph with the same number of vertices. Traverse the given graph. Here we are using the adjacency list to represent the graph. Traverse each adjacency list and while traversing keep adding the reverse edges (making source as destination and destination as source). See the code for better understanding.




import java.util.LinkedList; public class Main { static class Graph { int vertices; LinkedList<Integer>[] adjList; public Graph(int vertices) { this.vertices = vertices; adjList = new LinkedList[vertices]; //Initialize lists for (int i = 0; i < vertices; i++) { adjList[i] = new LinkedList<>(); } } public void addEdge(int source, int destination) { //add forward edge adjList[source].addFirst(destination); } public Graph reverse(Graph graph){ Graph reverseGraph = new Graph(vertices); for (int i = 0; i <vertices ; i++) { LinkedList<Integer> nodeList = adjList[i]; int source = i; for (int j = 0; j <nodeList.size() ; j++) { int destination = nodeList.get(j); //add reverse node reverseGraph.addEdge(destination, source); } } return reverseGraph; } public void printGraph(){ for (int i = 0; i <vertices ; i++) { LinkedList<Integer> nodeList = adjList[i]; System.out.println("Vertex connected from vertex: "+i); for (int j = 0; j <nodeList.size() ; j++) { System.out.print("->" + nodeList.get(j)); } System.out.println(); } } } public static void main(String[] args) { Graph graph = new Graph(5); graph.addEdge(0,1); graph.addEdge(1, 2); graph.addEdge(1, 3); graph.addEdge(2, 3); graph.addEdge(3, 4); graph.addEdge(4, 0); System.out.println("---------------Original Graph---------------------------"); graph.printGraph(); Graph reverseGraph = graph.reverse(graph); System.out.println("---------------Reverse Graph---------------------------"); reverseGraph.printGraph(); } }



from collections import defaultdict class Graph: def __init__(self, vertices): self.vertices = vertices self.adjList = defaultdict(list) def addEdge(self, source, destination): # Add forward edge self.adjList[source].append(destination) def reverse(self): reverseGraph = Graph(self.vertices) for i in range(self.vertices): nodeList = self.adjList[i] source = i for j in range(len(nodeList)): destination = nodeList[j] # Add reverse edge reverseGraph.addEdge(destination, source) return reverseGraph def printGraph(self): for i in range(self.vertices): nodeList = self.adjList[i] print(f"Vertex connected from vertex {i}:") for j in range(len(nodeList)): print(f"->{nodeList[j]}", end="") print() if __name__ == "__main__": graph = Graph(5) graph.addEdge(0, 1) graph.addEdge(1, 2) graph.addEdge(1, 3) graph.addEdge(2, 3) graph.addEdge(3, 4) graph.addEdge(4, 0) print("---------------Original Graph---------------------------") graph.printGraph() reverseGraph = graph.reverse() print("---------------Reverse Graph---------------------------") reverseGraph.printGraph()



package main type Graph struct { vertices int adjList map[int][]int } func NewGraph(vertices int) *Graph { return &Graph{ vertices: vertices, adjList: make(map[int][]int), } } func (g *Graph) addEdge(source, destination int) { g.adjList[source] = append(g.adjList[source], destination) } func (g *Graph) reverse() *Graph { reverseGraph := NewGraph(g.vertices) for i := 0; i < g.vertices; i++ { nodeList := g.adjList[i] source := i for j := 0; j < len(nodeList); j++ { destination := nodeList[j] reverseGraph.addEdge(destination, source) } } return reverseGraph } func (g *Graph) printGraph() { for i := 0; i < g.vertices; i++ { nodeList := g.adjList[i] println("Vertex connected from vertex", i) for j := 0; j < len(nodeList); j++ { println("->", nodeList[j]) } println() } } func main() { graph := NewGraph(5) graph.addEdge(0, 1) graph.addEdge(1, 2) graph.addEdge(1, 3) graph.addEdge(2, 3) graph.addEdge(3, 4) graph.addEdge(4, 0) println("---------------Original Graph---------------------------") graph.printGraph() reverseGraph := graph.reverse() println("---------------Reverse Graph---------------------------") reverseGraph.printGraph() }

Output:

---------------Original Graph---------------------------
Vertex connected from vertex: 0
->1
Vertex connected from vertex: 1
->3->2
Vertex connected from vertex: 2
->3
Vertex connected from vertex: 3
->4
Vertex connected from vertex: 4
->0
---------------Reverse Graph---------------------------
Vertex connected from vertex: 0
->4
Vertex connected from vertex: 1
->0
Vertex connected from vertex: 2
->1
Vertex connected from vertex: 3
->2->1
Vertex connected from vertex: 4
->3