Teaching Kids Programming – Reverse a Graph (Adjacency List)

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a directed graph represented as an adjacency list, return its reverse so if an edge goes from A to B, it now goes from B to A.

Each list in the adjacency list should be sorted in ascending order.

Constraints
0 ≤ n, m ≤ 250 where n is the number of rows and m is the maximum number of columns in graph

Algorithm to Reverse a Graph (Adjacency List)

A graph (noted as G(V, E) where V is set of vertices and E is set of edges) is a data structure that can be reprsented by Adjacency Matrix or Adjacency List. We can reverse a Graph by two steps. First, clone all the vertices and then iterate each edge in original Graph and add their reversed edges into the new Graph.

class Solution:
    def reverseGraph(self, graph):
        # create the Graph with just vertices
        rev = [[] for _ in range(len(graph))]
        for u, v in enumerate(graph):
            for k in v: # iterate over each edge
                rev[k].append(u) # add reversed edge
        return rev

The time and space complexity is O(VE).

See also: Algorithms to Reverse a Graph (Adjacency List)

–EOF (The Ultimate Computing & Technology Blog) —