Depth-first search (DFS)

In short, graph searches traverse a graph to map its structure. In this section, we will learn about an algorithm to accomplish such a search. Mapping out the structure of a graph can be important on its own, but it is a sub-problem that algorithms must solve in order to solve larger problems in graphs, as we have discussed. The DFS algorithm is quite possibly the most common approach for graph searches; it is an efficient method, and it is used as a subroutine in many more complex algorithms.

DFS starts at a source vertex, traverses the first available edge to visit another vertex, and repeats this until there are no edges leading to unvisited vertices—that is, until it has gone as deep as possible. At this time, it backtracks to the last vertex that has unvisited neighbors and takes another trip from that vertex through as many unvisited vertices until it reaches another dead end. It then backtracks and travels to unvisited vertices again and again...