3
$\begingroup$

Why do we use a last-in-first-out (LIFO) queue in the depth-first search algorithm?

In the breadth-first search algorithm, we use a first-in-first-out (FIFO) queue, so I am confused.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
1
$\begingroup$

We use the LIFO queue, i.e. stack, for implementation of the depth-first search algorithm because depth-first search always expands the deepest node in the current frontier of the search tree.

Norvig and Russell write in section 3.4.3

The search proceeds immediately to the deepest level of the search tree, where the nodes have no successors. As those nodes are expanded, they are dropped from the frontier, so then the search "backs up" to the next deepest node that still has unexplored successors.

A LIFO queue means that the most recently generated node is chosen for expansion. This must be the deepest unexpanded node because it is one deeper than its parent — which, in turn, was the deepest unexpanded node when it was selected.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .