7.9

(a) Adjacency matrix → adjacency lists
Algorithm: for every vertex u scan row u of the n × n matrix and append every vertex v with A[u][v]=1 to Adj[u].
for u in 0..n-1:
  Adj[u] ← []
  for v in 0..n-1:
    if A[u][v]==1: Adj[u].append(v)
Cost: the whole matrix is inspected once ⇒ Θ(n²).

(b) Adjacency lists → incidence matrix
We number the edges while scanning the lists and create two 1-entries per edge.
M ← zero matrix n × m
edge_id ← 0
for u in 0..n-1:
  for v in Adj[u]: # each edge appears twice
    if v > u: # keep only (u,v) with u<v
      M[u][edge_id] ← 1
      M[v][edge_id] ← 1
      edge_id += 1
Cost: every adjacency-list entry is touched once ⇒ Θ(n + m). (Writing the 1’s is O(m). The allocated matrix itself is n×m but filling it is still Θ(n+m).)

(c) Incidence matrix → adjacency lists
For each column find the two vertices that have a 1 and link them in both lists.
for u in 0..n-1: Adj[u] ← []
for e in 0..m-1:
  endpoints ← []
  for u in 0..n-1:
    if M[u][e]==1: endpoints.append(u)
  u,v = endpoints # exactly two in an undirected graph
  Adj[u].append(v)
  Adj[v].append(u)
Cost: each of the n×m entries is examined once ⇒ Θ(n·m).

Summary:
• (a) Θ(n²) • (b) Θ(n+m) • (c) Θ(n m)

Back to Chapter 7