Breath First Search

ALGORITHM BFS(G)//Implements a breadth-first search traversal of a given graph
//Input: Graph G = V, E//Output: Graph G with its vertices marked with consecutive //integers in the order they are visited by the BFS traversal
mark each vertex in V with 0 as a mark of being “unvisited”count ← 0for each vertex v in V do
if v is marked with 0Bfs(v)


Algorithm Bfs(v)//visits all the unvisited vertices connected to vertex v//by a path and numbers them in the order they are visited
//via global variable count
count← count + 1; 
mark v with count and initialize a queue with vwhile the queue is not empty do
for each vertex w in V adjacent to the front vertex do
if w is marked with 0count ← count + 1; 
mark w with the countadd w to the queue
remove the front vertex from the queue


C program:

#include<stdio.h>
int count=0;
int n;
void bfs(int a[][n],int b[],int v);
main()
{
    int i,j;
    printf("\nEnter number of vertices:");
    scanf("%d",&n);
    int a[n][n];
    int b[n];
    for(i=0;i<n;i++)
    {

        for(j=0;j<n;j++)
        {
            printf("\nEnter connection bt vertex %c & vertex %c",i+65,j+65);
            scanf("%d",&a[i][j]);
        }
    }
    for(i=0;i<n;i++)
   {

       for(j=0;j<n;j++)
       {
           printf("%d\t",a[i][j]);
       }
       printf("\n");
   }
   for(i=0;i<n;i++)
        b[i]=0;
                bfs(a,b,0);

}
void bfs(int a[][n],int b[],int v)
{

    int i,r=0,f=-1;
    int q[n];
    count++;
    b[v]=count;
    q[++f]=v;
     do
    {
        v=q[r];
        for(i=0;i<n;i++)
        {
            if(a[v][i]==1)
            {
                if(b[i]==0)
                {
                    count++;
                    b[i]=count;
                    q[++f]=i;
                }
            }
        }
       printf("%c\n",q[r++]+65);
    }while(f>=r);
}


Output:

Enter number of vertices:4

Enter connection bt vertex A & vertex A0

Enter connection bt vertex A & vertex B1

Enter connection bt vertex A & vertex C0

Enter connection bt vertex A & vertex D0

Enter connection bt vertex B & vertex A1

Enter connection bt vertex B & vertex B0

Enter connection bt vertex B & vertex C1

Enter connection bt vertex B & vertex D0

Enter connection bt vertex C & vertex A0

Enter connection bt vertex C & vertex B1

Enter connection bt vertex C & vertex C0

Enter connection bt vertex C & vertex D1

Enter connection bt vertex D & vertex A1

Enter connection bt vertex D & vertex B0

Enter connection bt vertex D & vertex C1

Enter connection bt vertex D & vertex D0
0       1       0       0
1       0       1       0
0       1       0       1
1       0       1       0
A
B
C
D

  

Read More