Graphs/Transitive Closure

Notes

The transitive closure of a directed graph G is denoted G*.

The transitive closure G* has all the same vertices as the graph G, but it has edges representing the paths from u to v.

If there is a directed path from u to v on G, there is a directed edge from u to v on the transitive closure G*.

Usefulness of Transitive Closure

The transitive closure G* of the graph helps us answer reachability questions fast.

Computing Transitive Closure

To compute the transitive closure, we need to find all possible paths, between all pairs u and v. We can do that using a BFS or a DFS.

Computing the transitive closure on an undirected graph is pretty trivial - equivalent to finding components.

Computing the transitive closure on a directed graph is not as trivial, but still straightforward (can still use a BFS or DFS).

An alternative method is to use the Graphs/Floyd Warshall algorithm: if we use a data structure for storing the graph that supports O(1) lookup time for finding if there is an edge between u and v, we can implement the Floyd-Warshall algorithm, which is potentially faster than computing DFS on every node.

For dense graphs or adjacency matrix representations, use Floyd-Warshall.

For sparse graphs, adjacency list/adjacency map representations, or very large graphs, use nested DFS.

Big O Cost

Performing a DFS or BFS costs $O(n+m)$, so performing a DFS or BFS on every node costs $O(n(n+m))$ (where n is number vertices and m is number of edges). Because number of edges is $O(n^{2})$, this gives an overall cost of $O(n^{3})$.

The Graphs/Floyd Warshall algorithm is also asymptotically $O(n^{3})$, but performs better for dense graphs and for graphs represented with an adjacency matrix data structure (see Graphs/Data Structures). It is also algorithmically simpler.