Regardless the input data structure's form, it must be traversable in depthfirst order (Figure ). A depth-first traversal operates over a set of nodes associated in pairwise fashion by a set of connectivity relationships, which are typically edges. Traversal proceeds by successively replacing each node as the center of focus, or root. Each new root is chosen from the untraversed neighbors of the current root. Eventually all nodes are processed, ending the traversal.