A graph search algorithm which tries all one-step extensions of current paths before trYing larger extensions. This requires all current paths to be kept in memorY simultaneouslY, or at least their end points. Opposite of depth-first search. See also {best first search}. (1996-01-05)