*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