/*In graph theory, Breadth First Search (BFS) is a technique for searching in a graph when search is limited to essentially two operations: (a) visit and inspect a node of a graph; (b) gain access to visit the nodes that neighbor the currently visited node. The BFS begins at a root node and inspects all the neighboring nodes. Then for each of those neighbor nodes in turn, it inspects their neighbor nodes which were unvisited, and so on. */
#include<stdio.h>
#include<conio.h>
int a[20][20],q[20],visited[20],n,i,j,f=0,r=-1;
void bfs(int v)
{ for(i=1;i<=n;i++)
if(a[v][i] && !visited[i])
q[++r]=i;
if(f<=r)
{ visited[q[f]]=1;
bfs(q[f++]);
}
}
Also Read : Program for implementing Depth First Search
int main()
{ int v;
printf(“\n Enter the number of vertices:”);
scanf(“%d”,&n);
for(i=1;i<=n;i++)
{ q[i]=0;
visited[i]=0;
}
printf(“\n Enter graph data in matrix form:\n”);
for(i=1;i<=n;i++)
{ for(j=1;j<=n;j++)
scanf(“%d”,&a[i][j]); }
printf(“\n Enter the starting vertex:”);
scanf(“%d”,&v);
bfs(v);
printf(“\n The node which are reachable are:\n”);
for(i=1;i<=n;i++)
if(visited[i])
printf(” %d\t”,i);
else
printf(“\n Breadth First Search is not possible”);
getch();
return 0;
}
Output:
You can check my other blog - CatchUpdates.com
You can connect with me on Instagram Or Quora And Linkedin as well.
- MongoDB Operators Tutorial – What are Different Operators Available? - October 5, 2019
- MongoDB Projection Tutorial : Return Specific Fields From Query - March 9, 2019
- MongoDB Index Tutorial – Create Index & MongoDB Index Types - July 6, 2018