DFS of Undirected Graphs

The depth-first search (DFS) technique is a method of scanning a finite, undirected graph. Since the publication of the papers of Hopcroft and Tarjan [4, 6], DFS has been widely recognized as a powerful technique for solving various graph problems. However, the algorithm has been known since the nineteenth century as a technique for threading mazes. See, for example, Lucas' report of Trémaux's work [5]. Another algorithm, which was suggested later by Tarry [7], is just as good for threading mazes, and in fact, DFS is a special case of it. But the additional structure of DFS is what makes the technique so useful.

Trémaux's Algorithm

Assume one is given a finite, connected graph G(V,E), which we will also refer to as the maze. Starting in one of the vertices, one wants to “walk” along the edges, from vertex to vertex, visit all vertices, and halt. We seek an algorithm that will guarantee that the whole graph will be scanned without wandering too long in the maze, and that the procedure will allow one to recognize when the task is done. However, before one starts walking in the maze, one does not know anything about its structure, and therefore, no preplanning is possible. So, decisions about where to go next must be made one by one as one goes along.

We will use “markers,” which will be placed in the maze to help one to recognize that one has returned to a place visited earlier and to make later decisions on where to go next.