Visual C++ - Depth First Search Algorithm

---

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

The look up begins with in the root node and keeps doing down towards left as far as possible along each branch before backtracking. Here is the Visual C++ code that implements Depth-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 Traverse_Depth_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 *dfs_head = new GraphNode(1);

void GraphNode::Traverse_Depth_First_Search_Tree()
{
   std::cout << m_data << "\n";
   for(int i = 0; i < m_maxChildren; i++)
      m_pChildren[i].Traverse_Depth_First_Search_Tree();
}

void Demo_Depth_First_Search_Tree()
{
   GraphNode *c1 = dfs_head->AddChild(2);
   GraphNode *c11 = c1->AddChild(3);
   c11->AddChild(4);
   c11->AddChild(5);

   GraphNode *c12 = c1->AddChild(6);

   GraphNode *c2 = dfs_head->AddChild(7);
   GraphNode *c3 = dfs_head->AddChild(8);
   GraphNode *c31 = c3->AddChild(9);
   c31->AddChild(10);
   c31->AddChild(11);

   GraphNode *c32 = c3->AddChild(12);

   std::cout << "Traversing in Depth First Search Order:\n";
   dfs_head->Traverse_Depth_First_Search_Tree();
}

void main()
{
   Demo_Depth_First_Search_Tree();
}
    

Output

Traversing in Depth First Search Order:
1
2
3
4
5
6
7
8
9
10
11
12

Press any key to continue . . .