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.