Reverse a directed graph

Problem

A directed graph consists of vertices and directed edges that connect these vertices. The task is to write an algorithm that computes the reversal of a directed graph. For any directed edge A -> B, you must reverse its direction to B -> A. The output graph should have all the edges reversed.

Examples

Example 1

Input:
Graph:
    A -> B
    B -> C 
    C -> D

Output:
Reversed Graph:
    A <- B
    B <- C 
    C <- D 

Explanation:
The original graph has edges:
- A → B → C → D
Reversing these edges gives:
- B ← A, C ← B, and D ← C.

Example 2

Input:
Graph:
    P -> Q
    Q -> R
    R -> S
    S -> P

Output:
Reversed Graph:
    P <- Q
    Q <- R
    R <- S
    S <- P

Explanation:
The original graph forms a cycle:
- P → Q → R → S → P.
Reversing these edges gives:
- Q ← P, R ← Q, S ← R, and P ← S.

Solution

Method 1 - Using Map

Quick points:

1. Graphs as adjacency lists: To efficiently represent the graph, we'll use adjacency lists. For each vertex, we will maintain a list of vertices it references.
2. Edge reversal: To reverse the graph, we examine all edges. If vertex u points to vertex v, then we reverse the edge to make v point to u. This involves reconstructing the adjacency list.

Approach

1. Input representation:

   • Use an adjacency list to represent the graph. For example:

     python graph = {
          'A': ['B'],
          'B': ['C'],
          'C': ['D']
      }
     

   • Here, the key represents a vertex, and the list of values represents vertices accessible from the key vertex.

2. Algorithm steps:
   • Create an empty adjacency list for the reversed graph.
   • Traverse each vertex and its edges in the original graph.
   • For each edge u -> v:
     • Add an entry in the reversed graph indicating v -> u.
   • Return the reversed graph.

Code

Java

public class Solution {
    public Map<String, List<String>> reverseGraph(Map<String, List<String>> graph) {
        // Initialize a new graph for the reversed edges
        Map<String, List<String>> reversedGraph = new HashMap<>();
        
        // Prepare reversedGraph with all nodes
        for (String node : graph.keySet()) {
            reversedGraph.put(node, new ArrayList<>());
        }
        
        // Traverse the original graph and reverse edges
        for (String node : graph.keySet()) {
            for (String neighbour : graph.get(node)) {
                reversedGraph.putIfAbsent(neighbour, new ArrayList<>());
                reversedGraph.get(neighbour).add(node);
            }
        }
        
        return reversedGraph;
    }

    // Example usage
    public static void main(String[] args) {
        Solution solution = new Solution();
        Map<String, List<String>> graph = new HashMap<>();
        graph.put("A", Arrays.asList("B"));
        graph.put("B", Arrays.asList("C"));
        graph.put("C", Arrays.asList("D"));

        Map<String, List<String>> reversedGraph = solution.reverseGraph(graph);
        System.out.println(reversedGraph);
    }
}

Python

python class Solution:
    def reverseGraph(self, graph):
        # Initialize a new graph for the reversed edges
        reversed_graph = {node: [] for node in graph}

        # Traverse the original graph and reverse edges
        for node in graph:
            for neighbour in graph[node]:
                if neighbour not in reversed_graph:
                    reversed_graph[neighbour] = []
                reversed_graph[neighbour].append(node)
        
        return reversed_graph


# Example usage
if __name__ == "__main__":
    solution = Solution()
    graph = {
        'A': ['B'],
        'B': ['C'],
        'C': ['D']
    }
    reversed_graph = solution.reverseGraph(graph)
    print(reversed_graph)

Complexity

• ⏰ Time complexity: O(V+E)
  • The algorithm visits each vertex and iterates through all its edges.
  • Let V be the number of vertices and E be the number of edges.
  • O(V + E) is the time complexity, as we process the adjacency list.
• 🧺 Space complexity: O(V+E)
  • We create a new adjacency list to store the reversed graph.
  • O(V + E) is the space complexity, accounting for all vertices and edges.