C++ Program for BFS Traversal

Hello Everyone!

In this tutorial, we will learn how to implement the BFS Traversal on a Graph, in the C++ programming language.

What is BFS Traversal?

As the name suggests, Breadth first search (DFS) algorithm starts with the starting node, and then traverse each branch of the graph until we all the nodes are explored at least once.

The algorithm explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level.

The data structure used in BFS is Queue. To learn more about the Queue data structure, we will recommend you to visit Queue Data Structure, where we have explained these concepts in detail.

For better understanding, refer to the well-commented C++ code given below.

Code:

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

vector<bool> v;
vector<vector<int>> g;

void bfsTraversal(int b)
{
    //Declare a queue to store all the nodes connected to b
    queue<int> q;

    //Insert b to queue
    q.push(b);

    //mark b as visited
    v[b] = true;

    cout << "\n\nThe BFS Traversal is:  ";

    while (!q.empty())
    {
        int a = q.front();
        q.pop(); //delete the first element form queue

        for (auto j = g[a].begin(); j != g[a].end(); j++)
        {
            if (!v[*j])
            {
                v[*j] = true;
                q.push(*j);
            }
        }
        cout << a << "  ";
    }
}

void makeEdge(int a, int b)
{
    g[a].push_back(b); //an edge from a to b (directed graph)
}

int main()
{
    cout << "\n\nWelcome to Studytonight :-)\n\n\n";
    cout << " =====  Program to demonstrate the Breadth First Search Algorithm, in CPP  ===== \n\n";

    cout << " =====  Note; The vertices are numbered from 0 to n-1.  ===== \n\n";

    int n, e;

    cout << "Enter the number of vertices: ";

    cin >> n;

    cout << "\n\nEnter the number of edges: ";

    cin >> e;

    v.assign(n, false);
    g.assign(n, vector<int>());

    int a, b, i;

    cout << "Enter the edges with source and target vetex: \n ";

    for (i = 0; i < e; i++)
    {
        cin >> a >> b;
        makeEdge(a, b);
    }

    for (i = 0; i < n; i++)
    {
        //if the node i is unvisited
        if (!v[i])
        {
            bfsTraversal(i);
        }
    }

    cout << "\n\n\n";

    return 0;
}

Output:

We hope that this post helped you develop a better understanding of the concept of BFS Traversal and its implementation in CPP. For any query, feel free to reach out to us via the comments section down below.

Keep Learning : )