Graphs/Transitive Closure: Difference between revisions
From charlesreid1
(Created page with "=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 pat...") |
No edit summary |
||
| Line 10: | Line 10: | ||
To compute the transitive closure, we nee a way to support O(1) lookups of whether an edge exists between u and v. | To compute the transitive closure, we nee a way to support O(1) lookups of whether an edge exists between u and v. | ||
=Flags= | |||
{{GraphsFlag}} | |||
Revision as of 12:49, 9 September 2017
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.
Flags
