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)