4. [10+10] The transpose of a directed graph G = (V,E) is the graph G (V,ET),...

Transcribed Image Text:

4. [10+10] The transpose of a directed graph G = (V,E) is the graph G (V,ET), where ET = {(v,u) V V(u, v) E}. Thus, GT is G with all its edges reversed. (a) Describe an efficient algorithm for computing GT from G for adja- cency list representation of G. (b) Describe an efficient algorithm for computing G from G for adja- cency matrix representation of G. 4. [10+10] The transpose of a directed graph G = (V,E) is the graph G (V,ET), where ET = {(v,u) V V(u, v) E}. Thus, GT is G with all its edges reversed. (a) Describe an efficient algorithm for computing GT from G for adja- cency list representation of G. (b) Describe an efficient algorithm for computing G from G for adja- cency matrix representation of G.