Graphs/Depth First Traversal: Difference between revisions
From charlesreid1
No edit summary |
(→Notes) |
||
| Line 7: | Line 7: | ||
A depth first traversal and search algorithm can be used as an algorithmic building block for a large number of problems. | A depth first traversal and search algorithm can be used as an algorithmic building block for a large number of problems. | ||
On an undirected graph, DFS can be used to : | DFS gives us: | ||
* paths | |||
* connectivity | |||
* cycles | |||
* spanning trees | |||
Specifically, we can get different things on directed vs. undirected graphs. | |||
On an undirected graph, DFS can be used to: | |||
* Find the path between two given vertices, or report that none exists | * Find the path between two given vertices, or report that none exists | ||
* Test whether a graph is connected | * Test whether a graph is connected | ||
| Line 13: | Line 21: | ||
* Find the connected components of a graph | * Find the connected components of a graph | ||
* Determine whether a graph has any cycles | * Determine whether a graph has any cycles | ||
On an undirected (connected) graph, to construct a spanning tree, do a DFS! | |||
On a directed graph, DFS can be used to: | On a directed graph, DFS can be used to: | ||
| Line 20: | Line 30: | ||
* Determine whether a graph has any cycles | * Determine whether a graph has any cycles | ||
* Compute the [[Graphs/Transitive Closure|transitive closure]] of a graph | * Compute the [[Graphs/Transitive Closure|transitive closure]] of a graph | ||
On a directed graph, to discover vertices reachable from a source vertex, do a DFS! To discover cycles, do a DFS and look for back-edges! | |||
Note that a depth-first search requires that we be able to mark vertices and/or edges are explored, and be able to test if they have been explored in O(1) time. This is easiest to do by augmenting the vertex class, but can also be done by creating a map of vertices to booleans or vertices to edges. | |||
=Resources= | =Resources= | ||
Revision as of 10:20, 5 September 2017
This page covers depth-first traversal and depth-first search on a graph.
Also see DFS
Notes
A depth first traversal and search algorithm can be used as an algorithmic building block for a large number of problems.
DFS gives us:
- paths
- connectivity
- cycles
- spanning trees
Specifically, we can get different things on directed vs. undirected graphs.
On an undirected graph, DFS can be used to:
- Find the path between two given vertices, or report that none exists
- Test whether a graph is connected
- Compute the spanning tree of a graph (which can, in turn, be used to bootstrap a minimum spanning tree)
- Find the connected components of a graph
- Determine whether a graph has any cycles
On an undirected (connected) graph, to construct a spanning tree, do a DFS!
On a directed graph, DFS can be used to:
- Find a directed path between two given vertices, or report that none exists
- Determine the set of reachable vertices from a source vertex
- Test whether a graph is strongly connected
- Determine whether a graph has any cycles
- Compute the transitive closure of a graph
On a directed graph, to discover vertices reachable from a source vertex, do a DFS! To discover cycles, do a DFS and look for back-edges!
Note that a depth-first search requires that we be able to mark vertices and/or edges are explored, and be able to test if they have been explored in O(1) time. This is easiest to do by augmenting the vertex class, but can also be done by creating a map of vertices to booleans or vertices to edges.
Resources
Flags
