  We exploit a decomposition of graph traversals to give a novel
characterization of depth-first and breadth-first traversals as universal
constructions. Specifically, we introduce functors from two different
categories of edge-ordered directed graphs into two different categories of
transitively closed edge-ordered graphs; one defines the lexicographic
depth-first traversal and the other the lexicographic breadth-first traversal.
We show that each functor factors as a composition of universal constructions,
and that the usual presentation of traversals as linear orders on vertices can
be recovered with the addition of an inclusion functor. Finally, we raise the
question of to what extent we can recover search algorithms from the
categorical description of the traversal they compute.
