5 Depth First Search

Given a graph G=V,EG=(V,E) and a vertex rVGr\in V(G), a depth-first search finds all the vertices vVGv\in V(G) for which there is a path from rr to vv. In other words, a depth-first search finds the connected component of GG that contains rr. It does so by starting at rr and systematically searching GG 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 rr that anchors the search is referred to as its root.

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

Depth First Search Topics