Depth first search

Depth first search

Algorithm;
1) place the header node into the open node stack (LIFO)
2) get the next item from the stack
3) check for a match of the search
4) push all child nodes that havent been visited into the stack in reverse 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);
};

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

  open.push_back(node);

  NodeList::reverse_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.rbegin();nit != node->children.rend();nit++)
        {
          Node* child = *nit;
          if(visited.find(child) == visited.end())
            {
              visited.insert(child);
              open.push_front(child);
            }
        }
    }
   return NULL;
}