Search

   
0.4.2.1 Depth-first traversal

Depth-first 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 path-building 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 next-previous 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.

Depth-first 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);
  }
}