5 Depth First Search

Given a graph $G=(V,E)$ and a vertex $r\in V(G)$, a depth-first search finds all the vertices $v\in V(G)$ for which there is a path from $r$ to $v$. In other words, a depth-first search finds the connected component of $G$ that contains $r$. It does so by starting at $r$ and systematically searching $G$ until no more vertices can be reached. After a vertex is reached by the search, it is referred to as visited. A vertex is explored after all adjacent vertices are visited. The vertex $r$ that anchors the search is referred to as its root.

When a depth-first search reaches vertex $v$, it immediately suspends its exploration of $v$ and explores any unvisited vertex $w$ adjacent to $v$. The exploration of $v$ resumes only after the exploration of $w$ has finished. The order in which a depth-first search visits a graph $G$ is a generalization of the order in which a preorder traversal visits the vertices of a tree. If $G$ is a tree, a depth-first search produces a preorder traversal of $G$.