  A traversal of a connected graph is a linear ordering of its vertices all of
whose initial segments induce connected subgraphs. Traversals, and their
refinements such as breadth-first and depth-first traversals, are computed by
various graph searching algorithms. We extend the theory of generic search and
breadth-first search from finite graphs to wellordered infinite graphs,
recovering the notion of "search trees" in this context. We also prove tight
upper bounds on the extent to which graph search and breadth-first search can
modify the order type of the original graph, as well as characterize the
traversals computed by these algorithms as lexicographically minimal.
