Breadth-First Search Algorithm and implementation in c++

BFS is most useful searching technique in database.In this technique,form the tree of data, corresponding child nodes of current state node is selected first during the searching process.Then in next step the childrens' of these selected child nodes will be searched.In this way exploring all nodes at a given depth before proceeding to the next level this searching method is implemented.

Algorithm

BFS uses a queue structure to hold all generate but still unexplored nodes. The order in which nodes are placed on the queue for removal and exploration determines the type of search. The BFS algorithm proceeds as follows.

1. Place the starting node s on the queue.
2. If the queue is empty, return failure and stop.
3. If the first element on the queue is a goal node g, return success and stop Otherwise,
4. Remove and expand the first element from the queue and place all the children at the end of the queue in any order.
5. Return to step 2.
   Source Code 
   #include <iostream>

   #include <ctime>

   using namespace std;

   struct node {

       int info;

       node *next;

   };

   
   

   class Queue {

       private:

           node *front;

           node *rear;

       public:

           Queue();

           ~Queue();

           bool isEmpty();

           void enqueue(int);

           int dequeue();

           void display();

   };

   void Queue::display(){

       node *p = new node;

       p = front;

       if(front == NULL){

           cout<<"\nNothing to Display\n";

       }else{

           while(p!=NULL){

               cout<<endl<<p->info;

               p = p->next;

           }

       }

   }

   Queue::Queue() {

       front = NULL;

       rear = NULL;

   }

   Queue::~Queue() {

       delete front;

   }

   void Queue::enqueue(int data) {

       node *temp = new node();

       temp->info = data;

       temp->next = NULL;

       if(front == NULL){

           front = temp;

       }else{

           rear->next = temp;

       }

       rear = temp;

   }

   int Queue::dequeue() {

       node *temp = new node();

       int value;

       if(front == NULL){

           cout<<"\nQueue is Emtpty\n";

       }else{

           temp = front;

           value = temp->info;

           front = front->next;

           delete temp;

       }

       return value;

   }

   bool Queue::isEmpty() {

       return (front == NULL);

   }

   class Graph {

       private:

           int n;

           int **A;

       public:

           Graph(int size = 2);

           ~Graph();

           bool isConnected(int, int);

           void addEdge(int x, int y);

           void BFS(int , int);

   };

   Graph::Graph(int size) {

       int i, j;

       if (size < 2) n = 2;

       else n = size;

       A = new int*[n];

       for (i = 0; i < n; ++i)

           A[i] = new int[n];

       for (i = 0; i < n; ++i)

           for (j = 0; j < n; ++j)

               A[i][j] = 0;

   }

   Graph::~Graph() {

       for (int i = 0; i < n; ++i)

       delete [] A[i];

       delete [] A;

   }

   bool Graph::isConnected(int x, int y) {

       return (A[x-1][y-1] == 1);

   }

   void Graph::addEdge(int x, int y) {

       A[x-1][y-1] = A[y-1][x-1] = 1;

   }

   void Graph::BFS(int x, int required) {

       Queue Q;

       bool *visited = new bool[n+1];

       int i;

       for (i = 1; i <= n; ++i)

       visited[i] = false;

       Q.enqueue(x);

       if(x == required) return;

       visited[x] = true;

       cout << "Breadth first Search starting from vertex ";

       cout << x << " : " << endl;

       while (!Q.isEmpty()) {

           int k = Q.dequeue();

           if(k == required){

               cout<<" FOUND HERE ";

               continue;

           }

           cout << k << " ";

           for (i = 1; i <= n; ++i)

               if (isConnected(k, i) && !visited[i]) {

                   Q.enqueue(i);

                   visited[i] = true;

               }

       }

       cout << endl;

       delete [] visited;

   }

   int main() {

       Graph g(12);

       g.addEdge(1, 2); g.addEdge(1, 3);

       g.addEdge(2, 4); g.addEdge(3, 4);

       g.addEdge(3, 6); g.addEdge(4 ,7);

       g.addEdge(5, 6); g.addEdge(5, 7);

       clock_t t1;

       t1 = clock();

       g.BFS(1, 15);

       float diff = (double)(clock() - t1)/CLOCKS_PER_SEC ;

       cout <<endl<< "The time taken for Breadth first search: "<< diff << endl;

   }