5 Depth First Search
Given a graph and a vertex , a depth-first search finds all the vertices for which there is a path from to . In other words, a depth-first search finds the connected component of that contains . It does so by starting at and systematically searching 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 that anchors the search is referred to as its root.
When a depth-first search reaches vertex , it immediately suspends its exploration of and explores any unvisited vertex adjacent to . The exploration of resumes only after the exploration of has finished. The order in which a depth-first search visits a graph is a generalization of the order in which a preorder traversal visits the vertices of a tree. If is a tree, a depth-first search produces a preorder traversal of .