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 , so performing a DFS or BFS on every node costs (where n is number vertices and m is number of edges). Because number of edges is , this gives an overall cost of .
The Graphs/Floyd Warshall algorithm is also asymptotically , 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.
Graphsnotes on graph theory, graph implementations, and graph algorithms
Part of Computer Science Notes
Series on Data Structures
Flags · Template:GraphsFlagBase · e