2. Give and analyse an algorithm for computing the square of a directed graph G given in (a) adjacency-list representation and (b) adjacency-matrix representation.
To compute G2 from the adjacency-list representation Adj of G, we perform the following for each Adj[u]:
for each vertex v in Adj[u]:
for each vertex w in Adj[v]
edge(u, w) ∈ E2
insert w in Adj2(u)
where Adj2 is the adjacency-list representation of G2 . For every edge in Adj we scan at most |V | vertices, thus we compute Adj2 in time O(V E).
After we have computed Adj2, we have to remove any duplicate edges from the lists (there may be more than one two-edge path in G between any two vertices). Removing duplicate edges is done in O(V +E0 ) where….