An important example of this is a tree: during a traversal it may be assumed that all "ancestor" vertices of the current vertex (and others depending on the algorithm) have already been visited.
Both the depth-first and breadth-first graph searches are adaptations of tree-based algorithms, distinguished primarily by the lack of a structurally determined "root" vertex and the addition of a data structure to record the traversal's visitation state.
This is easily accomplished by iterating through all the vertices of the graph, performing the algorithm on each vertex that is still unvisited when examined.
The algorithm then backtracks along previously visited vertices, until it finds a vertex connected to yet more uncharted territory.
DFS is the basis for many graph-related algorithms, including topological sorts and planarity testing.
The goal is to visit all n vertices and return to the starting vertex, but the sum of the weights of the tour should be as small as possible.
A probabilistic proof was used by Aleliunas et al. to show that there exists a universal traversal sequence with number of instructions proportional to O(n5) for any regular graph with n vertices.