Graphs/Depth First Traversal: Difference between revisions
From charlesreid1
(Created page with "Also see DFS =Notes= =Resources= ==Flags== {{GraphsFlag}} Category:DFS Category:Recursion") |
No edit summary |
||
| Line 1: | Line 1: | ||
This page covers depth-first traversal and depth-first search on a graph. | |||
Also see [[DFS]] | Also see [[DFS]] | ||
=Notes= | =Notes= | ||
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 : | |||
* 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 [[Graphs/Minimum Spanning Tree|minimum spanning tree]]) | |||
* Find the connected components of a graph | |||
* Determine whether a graph has any cycles | |||
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 [[Graphs/Transitive Closure|transitive closure]] of a graph | |||
=Resources= | =Resources= | ||
Revision as of 10:17, 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.
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 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
Resources
Flags
