7.27

To build [math]G^{R}[/math] in linear time just scan every vertex once and move each outgoing edge to the appropriate list of the opposite endpoint.

Algorithm (pseudocode):
Input: adj[1‥n]   // adj[u] is a list of vertices v with (u,v)∈E
Output: radj[1‥n] // adjacency lists of GR

for u = 1 to n:
   radj[u] ← ∅
for u = 1 to n:
   for each v in adj[u]:
      append u to radj[v] // adds the reversed edge (v,u)
return radj

Python illustration:
def reverse_graph(adj):
  n = len(adj)
  radj = [[] for _ in range(n)]
  for u in range(n):
    for v in adj[u]:
      radj[v].append(u)
  return radj

Correctness: Each original edge (u,v) is visited exactly once and inserted as (v,u) in [math]G^{R}[/math]; hence every reversed edge appears and nothing else is added.

Complexity: Initializing radj costs [math]O(n)[/math]. The nested loops examine each of the [math]m[/math] edges once, so the total running time is [math]O(n+m)[/math]. The algorithm uses [math]O(n+m)[/math] memory for the new adjacency lists.

Back to Chapter 7