breadth-first search

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.