Depth first

By making ${Q}$ a stack (Last-In, First-Out; or LIFO), aggressive exploration of the state transition graph occurs, as opposed to the uniform expansion of breadth-first search. The resulting variant is called depth-first search because the search dives quickly into the graph. The preference is toward investigating longer plans very early. Although this aggressive behavior might seem desirable, note that the particular choice of longer plans is arbitrary. Actions are applied in the forall loop in whatever order they happen to be defined. Once again, if a state is revisited, there is no work to do in line 12. Depth-first search is systematic for any finite $X$ but not for an infinite $X$ because it could behave like Figure 2.3a. The search could easily focus on one ``direction'' and completely miss large portions of the search space as the number of iterations tends to infinity. The running time of depth first search is also $O(\vert V\vert+\vert E\vert)$.