Introduction

Reversing a directed graph means creating a new graph in which every edge u -> v becomes v -> u. If the graph is stored as adjacency lists, this can be done in linear time, O(V + E), because you visit each vertex once and each edge once.

Why the Linear-Time Bound Is Possible

For adjacency-list graphs, the input already organizes outgoing edges by source vertex. Reversal only requires scanning those lists and appending reversed edges into a new adjacency list structure.

You do not need any expensive search or sorting step. The work is proportional to the size of the graph representation itself.

Python Example with Adjacency Lists

Suppose the graph is a dictionary mapping each node to a list of outgoing neighbors.

1def reverse_graph(graph):
2    reversed_graph = {node: [] for node in graph}
3
4    for source, neighbors in graph.items():
5        for target in neighbors:
6            reversed_graph[target].append(source)
7
8    return reversed_graph
9
10
11graph = {
12    "A": ["B", "C"],
13    "B": ["C"],
14    "C": []
15}
16
17print(reverse_graph(graph))

Output:

{'A': [], 'B': ['A'], 'C': ['A', 'B']}

Every original edge is processed exactly once.

Watch the Vertex Set Carefully

The code above assumes every vertex already appears as a key in the dictionary, even if it has no outgoing edges. That is important because the reversed graph still needs entries for sink nodes and isolated nodes.

If your input representation omits vertices with empty adjacency lists, add them first or discover them while scanning edges.

Example in C++

The same idea works naturally with vectors.

1#include <iostream>
2#include <vector>
3
4std::vector<std::vector<int>> reverse_graph(const std::vector<std::vector<int>>& graph) {
5    std::vector<std::vector<int>> reversed(graph.size());
6
7    for (int u = 0; u < static_cast<int>(graph.size()); ++u) {
8        for (int v : graph[u]) {
9            reversed[v].push_back(u);
10        }
11    }
12
13    return reversed;
14}
15
16int main() {
17    std::vector<std::vector<int>> graph = {
18        {1, 2},
19        {2},
20        {}
21    };
22
23    auto reversed = reverse_graph(graph);
24    for (int i = 0; i < static_cast<int>(reversed.size()); ++i) {
25        std::cout << i << ": ";
26        for (int v : reversed[i]) std::cout << v << ' ';
27        std::cout << '\n';
28    }
29}

This is still O(V + E) because the nested loop touches each stored edge once.

Why This Matters in Real Algorithms

Graph reversal is not just a toy transformation. It appears in algorithms such as:

• Kosaraju’s strongly connected components algorithm
• reverse reachability analysis
• computing predecessor relationships in control-flow graphs
• solving dependency questions from the opposite direction

So the linear-time transpose operation is often a core building block.

Adjacency Matrix Case

If the graph is stored as an adjacency matrix, reversal is just matrix transpose. But that representation has different complexity characteristics because the matrix already uses O(V^2) space. In that case, “linear time” relative to the matrix representation means something different from adjacency-list linear time.

For sparse graphs, adjacency lists are usually the better fit.

Common Pitfalls

A common mistake is forgetting to create empty adjacency lists for vertices that have no incoming edges in the reversed graph. Another is writing an algorithm that repeatedly searches for incoming edges, which degrades performance toward O(V * E) or worse. Developers also sometimes mix up graph reversal with undirected-edge duplication, but reversal matters only for directed graphs because edge direction actually changes.

Summary

• Reverse a directed graph by scanning every edge and flipping its direction.
• With adjacency lists, the operation is O(V + E).
• Initialize the reversed graph with all vertices, including those with no neighbors.
• The technique is a standard building block in SCC and reverse-reachability algorithms.
• Avoid repeated searches for incoming edges; one pass over the edge set is enough.