Transitive closure

The transitive closure of a directed graph G = (V, E) is a graph G* = (V, E*) that has an edge (i, j) whenever there is a path of any length from vertex i to vertex j in G. It is stored as a Boolean matrix P where P[i][j] = 1 if j is reachable from i. It tells which vertices can reach which others, and is computed with Warshall's algorithm in O(n³).

Example: edges a→b, b→c give transitive closure edges a→b, b→c and a→c.