Depth-first search [9] can be viewed as the opposite of BFS [7].
Depth-First Search.
Depth-first search (DFS) is an algorithm that explores a tree or graph data structure.
Geffner, "Learning
depth-first search: a unified approach to heuristic search in deterministic and non-deterministic settings, and its application to MDPs," in Proceedings of the 16th International Conference on Automated Planning and Scheduling (ICAPS06),D.Long, S.
For
depth-first search, the software had to offer ways for the user to mark vertices, move from the current vertex to a neighbor of it, and maintain a stack of vertices.
Clearly, it is not the algorithm itself, which, as described previously, is a forward-chaining algorithm with a
depth-first search strategy.
Tarjan's algorithm performs a bottom up traversal of the
depth-first search tree, identifying inner (nested) loops first.
This is understandable for a method based on
depth-first search. Improved word-ordering heuristics might reduce the fraction of such cases.
In
depth-first search, an actor would make plans for the future by devising chains of alternatives.
This algorithm uses
depth-first search, a systematic way of exploring a graph and visiting each vertex and edge.