Graphs/Transitive Closure
From charlesreid1
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*.
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.