Algorithms to Reverse a Graph (Adjacency List)

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.

Example 1
Input

1 2 3 4 5

graph = [     [1],     [2],     [] ]

graph = [
    [1],
    [2],
    []
]

Output

1 2 3 4 5

[     [],     [0],     [1] ]

[
    [],
    [0],
    [1]
]

Explanation
In this example the nodes start off 0 -> 1 -> 2 and then become 0 <- 1 <- 2.

Algorithm to Reverse the Graph

Let’s go through the Adjacency List of the Graph and reverse the edges and store them in a new Adjacency List.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

vector<vector<int>> reverseGraph(vector&l;tvector<int>>& graph) {
    vector<vector<int>> res(graph.size());
    unordered_map<int, vector<int>> G;
    for (int e = 0; e < graph.size(); ++ e) {
        auto nodes = graph[e];
        for (auto &n: nodes) {
            G[n].push_back(e);
        }
    }
    for (auto &[a, b]: G) {
        for (auto &n: b) {
            res[a].push_back(n);
        }
    }
    return res;
}

vector<vector<int>> reverseGraph(vector&l;tvector<int>>& graph) {
    vector<vector<int>> res(graph.size());
    unordered_map<int, vector<int>> G;
    for (int e = 0; e < graph.size(); ++ e) {
        auto nodes = graph[e];
        for (auto &n: nodes) {
            G[n].push_back(e);
        }
    }
    for (auto &[a, b]: G) {
        for (auto &n: b) {
            res[a].push_back(n);
        }
    }
    return res;
}

The complexity is O(NE) where N is the number of vertices and E is the number of the edges for each vertex. The space complexity is also O(NE) as the number of edges won’t change (except the directions).

We can directly reverse the edges into the result Adjacency List.

1
2
3
4
5
6
7
8
9
10

vector<vector<int>> reverseGraph(vector&l;tvector<int>>& graph) {
    int n = graph.size();
    vector<vector<int>> ans(n);
    for (int i = 0; i < n; ++i) {
        for (auto& j : graph[i]) {
            ans[j].push_back(i);
        }
    }
    return ans;
}

vector<vector<int>> reverseGraph(vector&l;tvector<int>>& graph) {
    int n = graph.size();
    vector<vector<int>> ans(n);
    for (int i = 0; i < n; ++i) {
        for (auto& j : graph[i]) {
            ans[j].push_back(i);
        }
    }
    return ans;
}

Reverse a Graph in Python: Teaching Kids Programming – Reverse a Graph (Adjacency List)

–EOF (The Ultimate Computing & Technology Blog) —