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 trivial.

Big O Cost

To compute the transitive closure, we nee a way to support O(1) lookups of whether an edge exists between u and v. This can be done using an adjacency matrix structure (see Graphs/Data_Structures). As long as we can support these O(1) lookups, we can construct the transitive closure in $ O(n(n+m)) $ time.

This cost comes from the fact that we are performing n graph traversals, each starting from a different vertex. We can use a DFS or a BFS, either one is $ O(n+m) $ cost.