Graphs/Depth First Traversal
From charlesreid1
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
