Depth-First Search

According to the Dictionary of Algorithms and Data Structures:

Depth-First Search, or DFS, is any search algorithm that considers outgoing edges (children) of a vertex before its siblings, that is, outgoing edges of the vertex's predecessor in the search. Extremes are searched first.

The main idea behind DFS is to explore deeper into the graph whenever possible. Starting at a vertex, DFS will take a path and explore it as far as it goes. It then backtracks until it reaches an unexplored neighbor (a branch on the path it has not explored yet). This process continues until every vertex that is reachable from the original source vertex has been discovered.

You have seen this behavior in pre-order and post-order tree traversal (and in-order binary tree traversal).

The process is further elaborated using a demo:

Demo

The following animated visualization of DFS algorithm (made by Gerry Jenkins) does a good job of illustrating its behavior:

Resources