Graphs/Transitive Closure: Difference between revisions
From charlesreid1
| (One intermediate revision by the same user not shown) | |||
| Line 19: | Line 19: | ||
Computing the transitive closure on a directed graph is not as trivial, but still straightforward (can still use a BFS or DFS). | 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== | ==Big O Cost== | ||
| Line 25: | Line 29: | ||
Performing a DFS or BFS costs <math>O(n+m)</math>, so performing a DFS or BFS on every node costs <math>O(n(n+m))</math> (where n is number vertices and m is number of edges). Because number of edges is <math>O(n^2)</math>, this gives an overall cost of <math>O(n^3)</math>. | Performing a DFS or BFS costs <math>O(n+m)</math>, so performing a DFS or BFS on every node costs <math>O(n(n+m))</math> (where n is number vertices and m is number of edges). Because number of edges is <math>O(n^2)</math>, this gives an overall cost of <math>O(n^3)</math>. | ||
The [[Graphs/Floyd Warshall]] algorithm is also asymptotically <math>O(n^3)</math>, but performs better for dense graphs and for graphs represented with an adjacency matrix | The [[Graphs/Floyd Warshall]] algorithm is also asymptotically <math>O(n^3)</math>, 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. | ||
=Flags= | =Flags= | ||
{{GraphsFlag}} | {{GraphsFlag}} | ||
Latest revision as of 13:59, 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*.
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 $ O(n+m) $, so performing a DFS or BFS on every node costs $ O(n(n+m)) $ (where n is number vertices and m is number of edges). Because number of edges is $ O(n^2) $, this gives an overall cost of $ O(n^3) $.
The Graphs/Floyd Warshall algorithm is also asymptotically $ O(n^3) $, 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.
Flags
