10.5 Transitive Closure

In 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³).