Algorithms: recursive and iterative depth first search

March 10, 2009 at 1:31 AMAndre Loker

I feel like blogging, but don’t have anything fancy to say – so why not talk about something basic as a graph searching algorithm?

The other day I needed to traverse a graph using depth first search – certainly not the most difficult thing in the world. A very basic recursive version can look like this:

   1: public void DfsRecursive(Node node) {
   2:   DoSomethingWithNode(node);
   3:   foreach(Transition t in node.Transitions){
   4:     Node destNode = t.Destination;
   5:     DfsRecursive(destNode);
   6:   }
   7: }

Assuming that a Node has a number of Transition instances that lead to the next node. BTW: I only consider trees here (i.e. graphs without loops). All snippets shown here can be used for graphs by keeping track of visited transitions and continue only for new ones (HashSet<Transition> is your friend).

My nodes did not contain the transitions as a list or array. Instead a node only had a link to the first transition, each transition had a link to the next transition – a linked list of transitions. Furthermore I needed to perform actions not only when a node was entered but also i) when the transition was followed, ii) when a transition was “undone” and iii) when a node was left. The latter two occur during the backtracking phase. Luckily with the recursive implementation, this was quite easy:

   1: public void Traverse(Node node) {
   2:   EnterNode(node);
   4:   var t = node.FirstTransition;
   5:   while(t != null) {
   6:     var destNode = TakeTransition(t);
   7:     Traverse(destNode);
   8:     UndoTransition(t);
   9:     t = t.NextSibling;
  10:   }
  12:   ExitNode(node);
  13: }

However, I needed to traverse very deep trees with depths of up to 500.000 nodes which made the recursive implementation unfeasible (it bails out with a StackOverflowException at graphs deeper than a couple of thousand nodes).

The “classical” iterative version of DFS looks like this:

   1: public void DfsIterative(Node node) {
   2:   var trail = new Stack<Transition>();
   3:   DoSomethingWithNode(node);
   4:   PushAllTransitionsToStack(node, trail);
   5:   while(trail.Count>0) {
   6:     Transition t = trail.Pop();
   7:     Node destination = t.Destination;
   8:     DoSomethingWithNode(destination);
   9:     PushAllTransitionsToStack(destination, trail);
  10:   }
  11: }

This is more or less what you will see when someone mentions iterative DFS. Note by the way that this version supports multiple transitions to the same destination node correctly – otherwise the algorithm could be even simpler. Also the order in which transitions of a node are visited is reversed.

The problem was that I needed to place my calls to UndoTransition and ExitNode somehow. Using the approach shown above makes that somewhat difficult. The problem is that the stack does not represent the actual path that is taken through the graph. Instead it contains transitions on the path as well as siblings that are yet to be visited. Interestingly enough I didn’t find something on the net the fitted my need – most sites mentioning iterative DFS use the approach described above. So, here’s what I came with after some time of thinking:

   1: public void Traverse(Node root) {
   2:   var trail = new Stack<Transition>();
   3:   EnterNode(root);
   4:   trail.Push(root.FirstTransition);
   6:   while(trail.Count > 0) {
   7:     Transition current = trail.Peek();
   9:     Node reachedNode = TakeTransition(current);
  10:     EnterNode(reachedNode);
  12:     // try to descend ... 
  13:     Transition next = reachedNode.FirstTransition;
  15:     // ... or backtrack
  16:     while(next == null && trail.Count > 0) {
  17:       Transition top = trail.Pop();
  18:       ExitNode(top.Destination);
  19:       UndoTransition(top);
  20:       next = top.NextSibling;
  21:     }
  23:     if(next != null) {
  24:       trail.Push(next);
  25:     }
  26:   }
  27:   ExitNode(root);
  28: }

What’s cool about this approach:

  • You can always tell the current depth of the traversal by simply checking trail.Count
  • Trail contains the exact path to the current node, so it’s easy to dump the trail for an interesting node

In my project I used some extensions to this basic version:

  • I used it to traverse graphs (not only trees), so I added a check whether a given state has already been visited before
  • I extended it to traverse over multiple graphs at once. Useful to explore the complete state space of the parallel composition of two graphs. Maybe I’ll go into details in a future post.

Is it something new? Certainly not. Is it rocket science? No! Could it be useful for you to have the skeleton of an iterative DFS with the ability to define backtracking actions at hand next time you need it? I hope so. Have fun!

Posted in: Snippets