depth-first search

A graph search that follows one path as deep as it can go, then backs up to the last choice point and tries the next branch.

In more detail

Recursive DFS uses the call stack; iterative DFS uses an explicit stack. A visited set stops it looping forever on cycles, and it runs in O(V + E). It is the basis of cycle detection, topological ordering and backtracking.

Related terms

Taught in

References