Perhaps the most fundamental graph problem is to traverse every edge and vertex in a graph in a systematic way. Indeed, most of the basic algorithms you will need for bookkeeping operations on graphs will be applications of graph traversal. These include:
Since any maze can be represented by a graph, where each junction is a vertex and each hallway an edge, any traversal algorithm must be powerful enough to get us out of an arbitrary maze. For efficiency, we must make sure we don't get lost in the maze and visit the same place repeatedly. By being careful, we can arrange to visit each edge exactly twice. For correctness, we must do the traversal in a systematic way to ensure that we don't miss anything. To guarantee that we get out of the maze, we must make sure our search takes us through every edge and vertex in the graph.
The key idea behind graph traversal is to mark each vertex when we first visit it and keep track of what we have not yet completely explored. Although bread crumbs or unraveled threads are used to mark visited places in fairy-tale mazes, we will rely on Boolean flags or enumerated types. Each vertex will always be in one of the following three states:
Obviously, a vertex cannot be completely-explored before we discover it, so over the course of the traversal the state of each vertex progresses from undiscovered to discovered to completely-explored.
We must also maintain a structure containing all the vertices that we have discovered but not yet completely explored. Initially, only a single start vertex is considered to have been discovered. To completely explore a vertex, we must evaluate each edge going out of it. If an edge goes to an undiscovered vertex, we mark it discovered and add it to the list of work to do. If an edge goes to a completely-explored vertex, we will ignore it, since further contemplation will tell us nothing new about the graph. We can also ignore any edge going to a discovered but not completely-explored vertex, since the destination must already reside on the list of vertices to completely explore.
Regardless of which order we use to fetch the next vertex to explore, each undirected edge will be considered exactly twice, once when each of its endpoints is explored. Directed edges will be consider only once, when exploring the source vertex. Every edge and vertex in the connected component must eventually be visited. Why? Suppose the traversal didn't visit everything, meaning that there exists a vertex u that remains unvisited whose neighbor v was visited. This neighbor v will eventually be explored, and we will certainly visit u when we do so. Thus we must find everything that is there to be found.
The order in which we explore the vertices depends upon the container data structure used to store the discovered but not completely-explored vertices. There are two important possibilities: