Graphs/Transitive Closure: Difference between revisions
From charlesreid1
No edit summary |
|||
| Line 9: | Line 9: | ||
==Big O Cost== | ==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. | 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 <math>O(n(n+m))</math> 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 <math>O(n+m)</math> cost. | |||
=Flags= | =Flags= | ||
{{GraphsFlag}} | {{GraphsFlag}} | ||
Revision as of 13:08, 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. 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.
Flags
