A search of a directed graph, and hence of a tree, conducted as follows. An initial starting vertex u is selected and visited. Then a (directed) edge (u, v) incident upon u is selected and a visit is made to v. Let x be the most recent vertex visited. Select some unexplored edge (x, y) incident upon x. If y has not been previously visited, visit y and proceed from there. If y has been previously visited select another edge incident upon x. Having completed the search through all paths beginning at y, return to x and continue to explore the edges incident upon x.

Depth-first searches of graphs play an important part in the design of efficient algorithms on graphs, in game theory, heuristic programming, and in artificial intelligence. See also iterative deepening.

Compare breadth-first search.