Breadth First Search algorithm in C++ language

Breadth - First Search (BFS) is a graph search/ traversal algorithm that begins from given initial node and visits all the neighboring nodes of each node of the given graph.  To implement BFS we are using QUEUE data structure which is further based on the principle of FIFO (First-IN-First-Out). 



Application of Breadth-First Search algorithm:
1. It is used to find all connected components in a Graph.
2. It is used to find all nodes within an individual connected component.
3. It is used to find the shortest path between any two nodes (unweighted or weighted graph)

Program Code:
#include<iostream>
#include<stdlib.h>
using namespace std;
int graph[10][10];
int i, j, k, vertices, edges;
int queue[10], front, rare, vertex;
int visit[10], visited[10];
int main()
{
cout <<"Enter number of vertices :";
cin >> vertices;
cout<<endl;
cout <<"Enter number of edges :";
cin >> edges;
cout<<endl;
cout <<" Enter Edges corresponding to your Graph : ";
cout<<endl;
for(k = 1; k <= edges; k++)
{
cin >>i>>j;
graph[i][j]=1;
}
cout <<"Enter initial vertex :";
cin >>vertex;
cout <<"Visitied vertices ";
cout<<endl;
cout <<vertex<<" ";
cout<<endl;
visited[vertex] = 1;
k = 1;
while(k < vertices)
{
for(j = 1; j <= vertices; j++)
if(graph[vertex][j] !=0 && visited[j] !=1 && visit[j] != 1)


{
visit[j] = 1;
queue[rare++] = j;
}
vertex = queue[front++];
cout<<vertex <<" ";
k++;
visit[vertex]=0; 
visited[vertex]=1;
}
return 0;
}

The output is tested on www.jdoodle.com
Output:
Enter number of vertices: 5
Enter number of edges : 7
Enter Edges corresponding to your Graph :
1 2
1 3
1 4
2 3
3 4
4 5


2 5
Enter initial vertex: 1
Visitied vertices 1 2 3 4 5 


Thanks
Mukesh Rajput

Mukesh Rajput

Mukesh Rajput

I am a Computer Engineer, a small amount of the programming tips as it’s my hobby, I love to travel and meet people so little about travel, a fashion lover and love to eat food, I am investing a good time to keep the body fit so little about fitness also..

Post A Comment:

0 comments:

Thanks
Mukesh Rajput