Breadth First Search Fri Sep 29 07:57:17 EDT 2006 Problem Help Breadth first search is most commonly used in maze problems, but can be used in other problems. The idea behind search is that one has a set of nodes, each node has a list of other nodes that are its children, and the search begins at a start node and progresses from the current node to one of its children until the search finds a goal node. The idea behind breadth first search is that one makes a `visited list' of the nodes in the order that they are first visited by the search, and one has a pointer into this list at the first node whose children have not yet been examined. Then one iteratively examines the child- ren of the node pointed at, adds any children that are not yet on the visited list to the end of the visited list, and bumps the pointer to the next node on the visited list. One stops when one gets to a goal node, or fails if one runs out of nodes to examine. (Depth first search is similar, except that the children are added to the visited list immediately after the node that is their parent, the node currently being examined for children. Depth first search with a visited list is almost unheard of in programming contests, but recursive exhaustive search which visits ALL nodes in depth first order is common.) There are three approaches to making a visited list: A. If the set of possible nodes is small and can be organized into an array, don't do breadth first search, but instead use dynamic programming. See the help file on dynamic programming. B. If the size of a node description is fixed and not large, and the maximum number of nodes that might be visited is not too large, make a large fixed size vector of nodes and two pointers: one to the next empty element and one to the first element whose children have not yet been examined. C. Otherwise allocate each node as it is visited. You will need a pointer in each node to the next node (or NULL if there is none), a pointer to the first node, a pointer to the last node, and a pointer to the first node whose children have not yet been examined. When an input test case is complete, you will need to deallocate all the nodes starting with the first node. Given your choice of visited list data structure, you need the following functions: 1. A function which given the parameters describing a node, determines whether the node is already in the visited list. This can be done by a linear search of the list. In some cases this is not fast enough, and a hash table is needed: see below. 2. A function which given the parameters describing a node creates a new node and adds it to the end of the visited list. 3. A function which checks a node to see if it is a goal node. 4. A function which given a node generates for each child of the node a call to function 1 to see if the child is on the visited list already, and if not, a call to function 2 to add the child to the list and then a call to function 3 to see if the added child is a goal. Given these it is easy to code the algorithm in a few lines. In order to construct the shortest path to the goal node, each node that is visited needs to record its parent. Then starting from the goal node and working backward a shortest path can be constructed. If a linear search of all the visited nodes is not fast enough, a hash table can be used. The idea of a hash table is that instead of having one long lookup list, we have many short lookup lists. Suppose we want M lookup lists. We write a hash function that takes the para- meters describing a node and returns an integer i, the hash value of the node, where 0 <= i < M. The node's hash value i names the lookup list on which the node will be placed. The hash table is a vector H such that H[i] is the head of lookup list i. Each node is now on two lists, a lookup list and the list of all visited nodes. Then the function to find a node in the visited list computes the node's hash value i and linearly searches just list H[i]. The function to put a node on the end of the visited list must computed the node's hash value i and add the node to the H[i] list. All this works well if for typical sets of actual nodes the hash function generates its M possible values about equally often. Then the expected length of each lookup list will be N/M, where N is the total number of nodes and M is the number of lookup lists. File: breadth_first_search Author: Bob Walton Date: See top of file. The authors have placed this file in the public domain; they make no warranty and accept no liability for this file. RCS Info (may not be true date or author): $Author: walton $ $Date: 2006/09/29 12:33:13 $ $RCSfile: breadth_first_search,v $ $Revision: 1.6 $