Breadth First Search in C++

Breadth First Search is an implementation of graph theory for searching in a graph by exploration of all the nodes available at a certain depth before jumping to next level. Also known as BFS, it is essentially based to two operations: approaching the node close to the recently visited node and inspecting and visiting any node.

Starting from the root node, this method leads to the solution by visiting and inspecting each and every neighbor nodes. In this tutorial, we’re going to discuss a simple program for Breadth First Search in C++ along with its algorithm, pseudo code, and sample output.

Breadth First Search is generally used when the shortest path is to be determined from one node to another node. It uses a queue during the process of searching. Since it visits or inspects a sibling node before inspection child nodes, it is sometimes considered to be the finest technique for traversing a definite or finite graph.

You can read more about BFS here.

Algorithm of Breadth First Search:

During the course of traversing a graph, Breadth First Search utilizes the queue data structure, which helps to store all the generates. These generates should be unexplored nodes only. The type of the search totally relies on the order of placing of nodes on the queue structure for exploration and removal. The algorithm of BFS goes like this:

1. Put the root node or starting node on queue (say q)
2. Examine the queue, whether it is empty or not.
   -> If the queue is void, return the failure and stop the searching process.
   -> Else proceed ahead by placing the direct child nodes that has not been discovered yet.

3. If the goal node (say g) is found as the first element of the queue, return it as success and stop.
4. Otherwise, removal and expansion of the first element of the queue is required. Place these newly generated offspring at the end of queue at any order.
5. Go back to the step 2 and repeat.

Pseudo code:

Consider an input graph ‘g’ and its root node ‘v’

1. Create a queue q
2. Place v onto ‘q’
3. Mark the root node ‘v’
4. while q is not empty:
5. t ← q.dequeue()
6. if r is the target or what you are searing: return r
7. for all edges e in g.adjacentEdges(r) do
8. o ← g.adjacentVertex(r,e)
9. if o is not marked: mark o
10. Place o onto q
11. return null

Lets consider a graph above given above. Applying the algorithm, the Breadth First Search from node 1 is: 1, 2, 3, 4, 6, 7, 5. The program given below for Breadth First Search in C++ gives the same as output.

Source Code of Breadth First Search in C++:

#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; // n represents the number of vertices in the graph
        int **A; // The function of A is storing the edge between two vertices
    public:
        Graph(int size = 2);
        ~Graph();
        bool isConnected(int, int);
        void addEdge(int u, int v);
        void BFS(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 u, int v) {
    return (A[u-1][v-1] == 1);
}

void Graph::addEdge(int u, int v) {
    A[u-1][v-1] = A[v-1][u-1] = 1;
}
void Graph::BFS(int s) {
    Queue Q;


    bool *explored = new bool[n+1];//  it Keeps track of explored vertices

    for (int i = 1; i <= n; ++i)// Initailization of  all vertices as unexplored
    explored[i] = false;
    Q.enqueue(s);// Pushing of  initial vertex to the queue
    explored[s] = true; // marking it as explored
    cout << "Breadth first Search starting from vertex ";
    cout << s << " : " << endl;

    //Unless the queue is empty is to be performed
    while (!Q.isEmpty()) {
        // Pop the vertex from the queue
        int v = Q.dequeue();

        //display the explored vertices
        cout << v << " ";

        //From the explored vertex v try to explore all the
        //connected vertices
        for (int w = 1; w <= n; ++w)

            /*Explores the vertex w if it is connected to v
            and and if it is unexplored*/
            if (isConnected(v, w) && !explored[w]) {
                //adds the vertex w to the queue
                Q.enqueue(w);
                //marks the vertex w as visited
                explored[w] = true;
            }
    }
    cout << endl;
    delete [] explored;
}

int main() {

    // Creates a graph with 12 vertices
    Graph g(12);

    //Adds edges to the graph */
    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();

    //Explores all vertices findable from vertex 1
    g.BFS(1);
    float diff = (double)(clock() - t1)/CLOCKS_PER_SEC ;
    cout <<endl<< "The time taken for Breadth first search: "<< diff << endl;
}

This source code of Breadth First Search in C++ mainly utilizes structures, data class and user defined function features of the C++ programming language. struct node  is the major structure used in the source code. The main functions used in the program are as follows:

• addEdge(1, 2)
• addEdge(1, 3)
• addEdge(2, 4)
• addEdge(3, 4)
• addEdge(3, 6)
• addEdge(4 ,7)
• addEdge(5, 6)
• addEdge(5, 7)
• clock()

Also see,
Depth First Search in C++
Dijkstra’s Algorithm Program
Gaussian Filter Generation in C++

The console output of Breadth First Search in C++ displays the starting vertex and the time taken to search. If you’ve any queries regarding BFS, its algorithm or source code, mention/discuss them in the comments section below.

You can find more C++ Tutorials here.