C++ Program for BFS Traversal














































C++ Program for BFS Traversal



Introduction:

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

Program:

#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 << " 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:

Enter the number of vertices: 5


Enter the number of edges: 5

 Enter the edges with source and target vetex:


01

02

 03

12

14

The BFS Traversal is: 0

1

2

3

 4





More Articles of Shaik Aftab Ahmed:

Name Views Likes
C++ Program to Find the Frequency of Odd & Even Numbers in the given Matrix 239 1
C++ program to Sort a Linked List Using Merge Sort 225 1
C++ Program to Implement a Linked List representation of a Binary tree 221 1
C++ Program to Check for balanced parentheses in an expression 146 1
C++ Program to Perform Inorder, Preorder, Postorder traversals in a binary tree. 181 1
C++ program to print Indian flag 201 1
C++ program to Convert a multi level linked list to a singly linked list 151 1
C++ program to print right view of a Binary tree using queue 163 1
C++ Program to implement Huffman Coding Compression Algorithm 225 1
C++ Program to Create a Height Balanced Binary Tree 160 1
C++ program to implement Prims algorithm 235 1
C++ Program for BFS Traversal 174 1
C++ Progam to Evaluate a Prefix Expression 167 1
C++ Program to Implement Queue using Linked List 175 1
C++ implementation of Stack using Linked list 173 1
C++ program to find the intersection point of two linked lists 228 1
C++ program to count the inversions in the given array 215 1
C++ program to perform D.N.F sort 227 1
C++ program to print all possible subsets of a String 215 1
C++ program to count the number of ones in a binary representation of a number 229 1
C++ program to print all possible subsets of a set 246 1
C++ program to find the largest word in a String 220 1
C++ Program to print a matrix in Spiral order 228 1
C++ program to convert from Binary to Decimal, Octal to Decimal, Hexadecimal to Decimal 227 1
C limits library 255 1
Program to add two Binary numbers 231 1

Comments