10.5 Transitive ClosureIn many applications we wish to determine if any two vertices in a graph are connected. This is usually done by finding the transitive closure of a graph. Formally, if G = (V, E) is a graph, then the transitive closure of G is defined as the graph G^{*} = (V, E^{*}), where E^{*} = {(v_{i}, v_{j})| there is a path from v_{i} to v_{j} in G}. We compute the transitive closure of a graph by computing the connectivity matrix A^{*}. The connectivity matrix of G is a matrix such that if there is a path from v_{i} to v_{j} or i = j, and otherwise. To compute A^{*} we assign a weight of 1 to each edge of E and use any of the all-pairs shortest paths algorithms on this weighted graph. Matrix A^{*} can be obtained from matrix D, where D is the solution to the all-pairs shortest paths problem, as follows: Another method for computing A^{*} is to use Floyd's algorithm on the adjacency matrix of G, replacing the min and + operations in line 7 of Algorithm 10.3 by logical or and logical and operations. In this case, we initially set a_{i}_{,}_{j} = 1 if i = j or (v_{i}, v_{j}) E, and a_{i,j} = 0 otherwise. Matrix A^{*} is obtained by setting if d_{i,j} = 0 and otherwise. The complexity of computing the transitive closure is Q(n^{3}). |