BFS

Program to implement Breadth First Search (BFS)

Algorithm

1. Place the starting node s on the queue.
2. If the queue is empty, return failure and stop.
3. If the first element on the queue is a goal node g, return success and stop Otherwise,
4. Remove and expand the first element from the queue and place all the children at the end of the queue in any order.
5. Return to step 2.
   
   
   Example:
                 Consider a graph

   

   Source Code:

   
   

   #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++]);

    }

   }

   void main()

   {

    int v;

    clrscr();

    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 <span id="IL_AD3" class="IL_AD">starting</span> 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 Bfs is not possible");

    getch();

   }