Breadth First Search in C++

Breadth First Search in C++ – Algorithm and Source Code

Basic Theory

Breadth – first searches are performed by exploring all nodes at a given depth before proceeding to the next level. This means that all immediate children of nodes are explored before any of the children’s children are considered. It has obvious advantage of always finding a minimal path length solution when one exists. However, a great many nodes may need to be explored before a solution is found, especially if the tree is very full.

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.
Example
Consider a graph
BFSGraph

Applying above algorithm, the BFS of the graph starting from node 1 is : 1, 2, 3, 4, 6, 7, 5

Source Code

#include 
#include  
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 Displayn";
    }else{
        while(p!=NULL){
            cout<<endl<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 Emtptyn";
    }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;
}

Complexity

The time complexity of the breadth-first search is O(bd). This can be seen by noting that all nodes up to the goal depth d are generated. Therefore, the number generated is b + b2 + . . . + bd which is O(bd). The space complexity is also O(bd) since all nodes at a given depth must be stored in order to generate the nodes at the next depth, that is, bd-1 nodes must be stored at depth d – 1 to generate nodes at depth d, which gives space complexity of O(bd).