Visual C++ - Breadth First Search Algorithm

---

Breadth-first search (BFS) is an algorithm for traversing or searching a tree or graph data structue.

The look up begins with in the root node and keeps searching its neighboring nodes before it moves down first. In other words, it keeps going down only after visiting all nodes in the same level. Here is the Visual C++ code that implements Beadth-First Search Algorithm in a Graph Tree Structure

V = nodes

E = Edges between pairs of Node

Worst Case Performance = O ( |V| + |E| )

#include 
#include 
#include 
#include 

class GraphNode
{
   int m_data;
   int m_maxChildren;
   int m_memorySpace;
   GraphNode *m_pChildren;
public:
   GraphNode(int data = 0);
   ~GraphNode();
   GraphNode* AddChild(int data);
   void Print_BSF_Node(std::deque < GraphNode* > &mylist);
   void Traverse_Breadth_First_Search_Tree();   
};

GraphNode::GraphNode(int data)
{
   m_data = data;
   m_maxChildren = 0;
   m_memorySpace = 0;
   m_pChildren = NULL;
}

GraphNode::~GraphNode()
{
   if(m_memorySpace > 0)
   {
      delete [] m_pChildren;
      m_maxChildren = 0;
      m_memorySpace = 0;
   }
}

GraphNode* GraphNode::AddChild(int data)
{
   if(m_memorySpace <= 0)
   {
      m_pChildren = new GraphNode[10];
      m_memorySpace = 10;
   }
   if(m_maxChildren >= 10)
      return NULL; // max of 10 children in this program
   GraphNode *pNode = &m_pChildren[m_maxChildren];
   m_pChildren[m_maxChildren] = data;
   m_maxChildren++;
   return pNode;
}

GraphNode *bfs_head = new GraphNode(1);

void GraphNode::Print_BSF_Node(std::deque < GraphNode* > &mylist)
{   
   std::cout << m_data << "\n";
   for(int i = 0; i < m_maxChildren; i++)
   {
      mylist.push_back(&m_pChildren[i]);
   }
}

void GraphNode::Traverse_Breadth_First_Search_Tree()
{   
   std::deque< GraphNode* > mylist;
   mylist.clear();

   mylist.push_back(this);

   while(mylist.size() > 0)
   {
      (*mylist.begin())->Print_BSF_Node(mylist);
      mylist.pop_front();
   }
}

void Demo_Breadth_First_Search_Tree()
{
   GraphNode *c1 = bfs_head->AddChild(2);
   GraphNode *c2 = bfs_head->AddChild(3);
   GraphNode *c3 = bfs_head->AddChild(4);

   GraphNode *c11 = c1->AddChild(5);
   GraphNode *c12 = c1->AddChild(6);
   GraphNode *c31 = c3->AddChild(7);
   GraphNode *c32 = c3->AddChild(8);

   c11->AddChild(9);
   c11->AddChild(10);
   c31->AddChild(11);
   c31->AddChild(12);

   std::cout << "Traversing in Breadth First Search Order:\n";
   bfs_head->Traverse_Breadth_First_Search_Tree();

}

void main()
{   
   Demo_Breadth_First_Search_Tree();
}

Output

Traversing in Breadth First Search Order:
1
2
3
4
5
6
7
8
9
10
11
12
Press any key to continue . . .