Depth-First Search

An ode to depth-first search

A fundamental need when working with graphs is to be able to search or process all vertices of the graph. It may be that we’re searching for some information stored on one or more nodes or that we want to determine if a graph is bipartite by $2$-coloring all of its vertices; or it may be that we want to write an algorithm for traversing a maze represented as a graph. The depth-first search (DFS) algorithm is the classical algorithm used and tailored for solving similar problems.

Depth-first search enjoys a special place in our hearts as a subroutine used in a myriad of other graph algorithms. We’ll see some of these algorithms in this chapter.

The basic idea

The big idea behind DFS is that we start at a vertex and move to an adjacent vertex that hasn’t been visited before. We keep going like this until we are stuck on a node, say $v^\prime$, all of whose neighbors have already been visited. We consider $v^\prime$ explored and resume the search from the preceding node, i.e., we backtrack to the node from where we first stepped onto $v^\prime$. We can once again ...