Cormen Edition 3 Exercise 22.1 Question 3 (Page No. 592)

Question

The transpose of a directed graph $G=(V,E)$ is the graph $G^T=(V,E^T)$, where $E^T=\{(v,u) \in V * V :(u,v) \in E \ \}$ .Thus ,$G^T$ is $G$ with all its edges reversed . Describe efficient algorithms for computing $G^T$ from $G$,for both the adjacency list and adjacency matrix representations of $G$. Analyze the running times of your algorithms.

Comments

Should it be $O(V^2)$ for Adjacency matrix and $O(E)$ for Adjacency list?

---

So, if you do not want to use any extra storage in case of an adjacency list, it should be O(VE). Because one has to search where each vertex appears in each list and create the transposed list. Whereas in the Adjacency matrix, all that one has to do is find the transpose of the matrix. So, that should be O(V).

Answer 1

# adjacency-list :

O(V+E)…

Iterate all the nodes, for each node i, mark its adjacency-list as L, then add i to all the nodes in L ...

 

## adjacency-matrix :

O(V*V)...

Just transpose the matrix …