23 views
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.
| 23 views
0
Should it be $O(V^2)$ for Adjacency matrix and $O(E)$ for Adjacency list?