Breadth first recursion

Problem: Find routes to everything, or find the shortest route there.

Solution: Maintain a queue of items to examine. When you find something you need to recurse into, put it on the end of the queue. Keep a list of things you've already done so you know what you do and don't need to recurse into.

Concepts of depth first and breadth first are confusing. First attempts at writing code to traverse a map, directory structure, and so forth, mix elements of both unsuccessfully.

  sub solve_maze {

  
    my $me = $_[0];
    my $dest = $_[1];

  
    return ($me) if $me eq $dest;

  
    my @queue = ($me);
    my %route = ($me => [$me]); 

  
    while(my $ob = shift @queue) {

  
      foreach my $i (@{$ob->neighbors()}) {

  
        if(!$route{$i}) {
          $route{$i} = [ @{$route{$ob}}, $i ];
          return \$route{$i} if($i eq $dest);
          push @queue, $i;
        }       

  
      }
    } 
  }

//@queue// is the list of directions we haven't taken yet, and need to get back to. We do them in the order found. When going through a directory structure on a filesystem, that would do the top level directories first, then the 2nd level ones, then the 3rd level, and so forth.

//%route// keeps track of what we've found, and how we've found it. Every node we find, we know the path to: the path to the current node plus the current neighbor we're examining. Initially, the current node is the root node, and all of its neighbors will have a two hop path: the root node, then the current neighbor. This pattern repeats for all of their neighbors.

For our purposes, we want to know the route used to get from one place to another: we return a list of steps taken to get there. We want the first match. There may be several paths. Removing the //return \$route...// line will find all of the routes, shortist routes first, without duplicates. Before the //if(!$route...// line, instead put:

  push @routes_to_dest, [ @{$route{$ob}}, $i ] if($i eq $dest);

That will log all routes we find, not merely the first.

Since BreadthFirst recurssion starts at the root and expands outward in all directions at the same rate, it is optimal for cases where the target and destination are near by.

DepthFirst recurssion is even easier to implement, and is optimal for cases where every node must be visited. It goes as far as it can in any one direction, then goes back until it finds another route. Since new tangets are taken as soon as they are found, there is no need to remember what has been done or what needs to be done - only where you were on previous routes when you took a tangent.

External Links

• http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/119466

The article is originally from Perl Design Patterns Book.

• DepthFirst[?]