0.4.2.1 Depthfirst traversal
Depthfirst searching, also sometimes known as backtracking, builds a
path from emanating at the starting point and continuing as far as
possible into the graph. Each new edge traversed must be one that has
not already been covered by the algorithm. The pathbuilding
operation continues until it reaches a point at which there is no edge
leading to a vertex that has not already been visited. At such a
point we backtrack to the previous node, choose a new edge from that
point, and build as long a path as possible from there. In
backtracking, if all the edges from the previous node have been tried
we backtrack again to the nextprevious node and so on. Eventually
this method will visit every node in a connected graph.
The actual traversal is often accomplished using a stack data structure.
First, the starting node is pushed onto the stack. Then the following
process repeats:
 Pop a node off the stack
 Traverse to this current node
 Push all nodes adjacent to the current node onto the stack
The process terminates when the stack is empty. The same process can
be implemented as a recursive function which uses the system stack
instead of a data segment structure.
Depthfirst traversal of a graph is an O(V + E) operation where Vis the number of vertices in the graph and E is the number of edges.
int visited[MAX_VERTS];
/*
* Assume visited[x] = 0 for all 0 <= x <= MAX_VERTS on first call.
*
*/
void df_traverse(int vertex) {
link t;
/*
* record the fact that we've visited this vertex,
* possibly call a special function here to do something more than
* simply mark it ``visited''
*
*/
visited[vertex] = 1;
/*
* traverse recursively at every vertex adjacent to vertex. This
* assumes an adjacency list representation of the graph.
*
*/
for (t = adj[k]; t != NULL; t = t>next) {
if (!visited[t>v]) df_traverse(t>v);
}
}
