Breath First Search

Breath first search

Algorithm;
1) place the header node into the open node queue (FIFO)
2) get the next item from the queue
3) check for a match of the search
4) push all child nodes that havent been visited into the queue in order
5) repeat from 2

Complexity:
The numbers are odd.. need to find out why..

class Node
{
public:
  string title;
  list children;

  Node(string _title);
  virtual ~Node();

  void addChild(Node* kid);
  Node& operator<<(Node& kid);
};

typedef list NodeList;
typedef set NodeTree;

Node* breath_first_search(Node* node, string target)
{
  NodeList open;
  NodeTree visited;

  open.push_back(node);

  NodeList::iterator nit;
  while(open.size() > 0)
    {
      node = open.front();
      open.pop_front();
      cout << node->title << " ";
      
      if(node->title == target)
        return node;
      
      for(nit = node->children.begin();nit != node->children.end();nit++)
        {
          Node* child = *nit;
          if(visited.find(child) == visited.end())
            {
              visited.insert(child);
              open.push_back(child);
            }
        }
    }
  return NULL;
}