Reading

These notes.

Homework

Work on your problem set 2 solutions!

A more careful depth-first search

In this section, we'll consider a slightly different version of depth-first search. We'll lose the "generic search" framework, but we'll gain a lot more information about the search. In particular, we'll get a closer connection to the underlying search tree, in which we'll explicitly see our search as doing a depth-first traversal of the underlying search tree where we have a clearly defined "current path" we are exploring in the graph. In class we more clearly defined what the difference is.

The initial version of this new depth-first search is a recursive formulation - nice and simple - which comes from the textbool Aho, Hopcroft and Ullman.

DFSVisit(G,u)
  mark u active
  for each v in children of u do
    if v is unvisited
      DFSVisit(G,v)
  mark u processed

In class we went over this algorithm and how it operates on the graph and starting vertex from the previous homework. As a recursive algorithm, understanding it means drawing the recursive call stack. When we did that, we saw that each call-stack record was associated with a vertex - the value "u" for that recursive call. Moreover, if you traverse all the vertices on the call stack from the bottom to the top, it forms a path in the graph: the "current search path".

One property we noticed was that if you are examining a child w of the current u and w is marked active, it means that there is a cycle in the graph. That's an interesting observation, and it gives us more cause to examine this algorithm.

An iterative version of DFSVisit

Any recursive algorithm can be made into an iterative algorithm - all you need to do is simulate the call stack with an explicit stack data structure. In the case of DFSVisit, there is good reason to want to do this, because the stack of vertices contains important information - the current path in the search - and normally you don't get access to the call stack in a recursive program. The trick (as we saw in class) is that on the stack we push not just a vertex u, but a pair (u,i) where us in the vertex, and i is a count of the number of children of u that have been examined so far.

In class you guys split into groups and tried putting this together on your own. Here's what we came up with.

DFSVisit(Graph G, vertex s) ← assume G is an adjacency list rep
initialize S to an empty stack of vertex-integer pairs
mar s active
S.push((s,0))
while S not empty do
  (u,i) = S.pop()
  if i is less than the number of neighbors of u
    S.push((u,i+1))
    v = G[u][i]
    if v is unvisited
      mark v active
      S.push((v,0))
  else
    mark u processed
	

Now we get this beautiful property that the stack S is precisely the path from root s down to the current vertex u in the search tree. Moreover, since only the vertices currently on the stack are marked active, we can check in constant time whether a given vertex is "on the current path" by checking its mark.