A graph-traversal
strategy that proceeds along a path from a given
vertex as deeply into the
graph as possible before backtracking. That is, after visiting a vertex, a DFS visits, if possible, an unvisited
adjacent vertex. If the traversal reaches a vertex that has no unvisited adjacent vertices, it backs up and then visits, if possible, an unvisited adjacent vertex. See also
breadth-first search.
The DFS strategy has a simple recursive form:
DFS(v)
// Traverses a graph beginning at vertex v by using a
// depth-first search: Recursive version.
Mark v as visited
for (each unvisited vertex u adjacent to v)
DFS(u)