Implementing BFS Traversal on a Graph

Introduction

In this lab, you will learn how to implement the BFS Traversal algorithm for a graph using C++. The BFS algorithm starts with a node in a graph and explores all the nodes at the present depth level before moving on to the nodes at the next level. BFS Traversal utilizes the data structure called Queue. We will be explaining the Queue data structure in detail, as well.

Setting up the project

Navigate to the project directory:

cd project

Create a new C++ file named main.cpp, using:

touch main.cpp

Including the necessary libraries

In C++, we use iostream for input and output, vector for storing elements dynamically, and queue for implementing the BFS Traversal algorithm. We also use bits/stdc++.h header file to include all the standard libraries. In the main.cpp file, type in the following code:

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

using namespace std;

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

Implementing the BFS Traversal Algorithm

We will create a function named bfsTraversal, which takes a starting node as an argument. This function will process the BFS Traversal algorithm.

void bfsTraversal(int b)
{
    queue<int> q; // Declare a queue to store all the nodes connected to b
    q.push(b); // Insert b to queue
    v[b] = true; // Mark b as visited

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

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

        // Loop through all the nodes that are connected to the current node
        for (auto j = g[a].begin(); j != g[a].end(); j++)
        {
            if (!v[*j])
            {
                v[*j] = true;
                q.push(*j); // Add the connected node to the queue for processing
            }
        }
        cout << a << "  ";
    }
}

Adding Edges to the Graph

We will create a function named makeEdge that takes two vertices and creates an edge between them. It will be called for each edge of the graph.

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

Accepting the Graph Information

In this step, we will accept the graph information from the user, including the number of vertices and edges, the edges' source and target vertices, and initialize the vectors.

int main()
{
    int n, e, a, b, i;

    cout << "Enter the number of vertices: ";
    cin >> n;

    cout << "Enter the number of edges: ";
    cin >> e;

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

    cout << "Enter the edges with source and target vertex: ";

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

    for (i = 0; i < n; i++)
    {
        if (!v[i])
        {
            bfsTraversal(i);
        }
    }

    return 0;
}

Compiling and Running the Program

The next step is to compile and run the code. In the terminal, run the following command:

g++ main.cpp -o main && ./main

You should be able to see the output of the graph's BFS Traversal algorithm on the terminal.

Full code of the main.cpp file

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

using namespace std;

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

void bfsTraversal(int b)
{
    queue<int> q;
    q.push(b);
    v[b] = true;

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

    while (!q.empty())
    {
        int a = q.front();
        q.pop();

        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);
}

int main()
{
    int n, e, a, b, i;

    cout << "Enter the number of vertices: ";
    cin >> n;

    cout << "Enter the number of edges: ";
    cin >> e;

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

    cout << "Enter the edges with source and target vertex: ";

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

    for (i = 0; i < n; i++)
    {
        if (!v[i])
        {
            bfsTraversal(i);
        }
    }

    return 0;
}

Summary

In this lab, you learned how to implement the BFS Traversal algorithm on a graph using C++. The algorithm starts with a starting node and explores all the nodes in the graph. We used a queue data structure for implementing the BFS algorithm. By completing this lab, you have developed a better understanding of Graph Traversal algorithms.