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
Comments