BFS algorithm introduction and implementation in C language

BFS algorithm:-

The full form of BFS is Breadth First Search. It is a graph traversal algorithm that starts traversing the graph from the starting or initial node and after that visits all the neighboring nodes. this process will continue for each of the neighbor node until it reaches the ending or last node. BFS uses Queue data structure.

बी.एफ.एस. का पूरा नाम ब्रेडथ फर्स्ट सर्च है। यह एक ग्राफ ट्रेवर्सल अल्गोरिथम है जिसमे प्रारंभिक नोड से ग्राफ को ट्रेवर्स किया जाता है इसके पश्चात् सभी पडोसी नोड्स को विजिट किया जाता है। यह प्रक्रिया सभी नोड्स पर तब तक चलती रहती है जब तक कि अंतिम नोड प्राप्त नहीं हो जाता। बी.एफ.एस.अल्गोरिथम के द्वारा क्यू डाटा स्ट्रक्चर का प्रयोग किया जाता है।       

Steps of BFS Algorithm (बी.एफ.एस.अल्गोरिथम के चरण):-

Step 1: SET STATUS = 1 (ready state) for each node in G

Step 2: Insert the starting node A and set its STATUS = 2 (waiting state)

Step 3: Repeat Steps 4 and 5 until Queue is empty

Step 4: Delete a node N. Process it and set its STATUS = 3 (processed state)

Step 5: Insert all the neighbors of N that are in the ready state (whose STATUS = 1) and set

their STATUS = 2 (waiting state)

Step 6: EXIT

Consider following graph :- 

निम्न ग्राफ को देखते है :-

C program for BFS algorithm:-

#include<stdio.h>
#include<conio.h>
int graph[20][20],q[20],vis[20],n,i,j,f=0,r=-1;
void bfs(int v)
{
 for(i=1;i<=n;i++)
 if(graph[v][i] && !vis[i])
 q[++r]=i;
 if(f<=r)
 {
 vis[q[f]]=1;
 bfs(q[f++]);
 }
}
void main(){
 int v;
 clrscr();
 printf("\n Enter the number of vertices:");
 scanf("%d",&n);
 for(i=1;i<=n;i++)
 {
  q[i]=0;
  vis[i]=0;
 }
 printf("\nEnter graph data in matrix form:\n");
 for(i=1;i<=n;i++)
 {
 for(j=1;j<=n;j++)
 scanf("%d",&graph[i][j]);
 }
 printf("\nEnter the starting node:");
 scanf("%d",&v);
 bfs(v);
 printf("\nThe node which are reachable are:\n");
 for(i=1;i<=n;i++){
  if(vis[i]) printf("%d\t",i);
  else printf("\n Bfs is not possible");
   }
 getch();
}