Thursday, 26 October 2017

Breadth First Search algorithm in C++ language

Breadth - First search (BFS) is a graph search/ traversal algorithm that begins from given initial node  and visit all the neighbouring 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 with in 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

No comments:

Post a Comment

Thanks
Mukesh Rajput