Stack-based graph traversal ≠ depth first search
I just finished teaching our required undergraduate algorithms class, and in grading their final exams I discovered that a few of the students have (not from me) acquired the incorrect belief that modifying the standard version of the breadth first search algorithm by replacing the stack with a queue makes it into depth first search. Embarrassingly, the Wikipedia depth first search article made the same mistake (until today), as do some textbooks (for example Skiena's Algorithm Design Manual p. 169; Jeff Edmonds' How to Think about Algorithms, pp. 175–178; Gilberg and Forouzan Data Structures: A Pseudocode Approach Using C, 2nd ed., p. 497).
In trees, or in AI search contexts where the visited set is not used to eliminate duplicate vertices, this idea does indeed produce a depth-first search. But in arbitrary graphs with a visited set, the traversal that you get from this routine is not depth first. The problem is that nodes high in the tree push some of their neighbors as children too early; in a proper depth first search those children would instead be discovered as descendants farther down in the tree. Here's an example, illustrating (as usual) the tree whose edges link each vertex with the earlier vertex it was discovered from:
In a depth first search tree, all edges connect ancestors and descendants. In a breadth-first search tree, all edges connect vertices in the same or adjacent levels. But in the stack traversal tree, all non-tree edges connect pairs of vertices that are not ancestors and descendants of each other, the opposite property to the depth first tree property. Or, to put it another way, if \( w \) is a descendant of \( v \), and is adjacent to \( v \), then \( w \) must be a direct child of \( v \).
