c program and algorithm of breath first search (BFS) of graph

 Algorithm:-

                   It work on queue.

      Step 1. Initialize all vertex to the Ready state.

      Step 2. Insert the stating vertex into queue and change it’s status to the waiting state.

      Step 3. Repeat step 4 and step 5 until stack is empty.

      Step 4. Delete the front vertex ‘n ‘ and process ‘n’ and change it’s status to the processed                        state.

      Step 5. Insert into queue all the neighbours  of the vertex ‘n’ that are still in ready state and                    change their status to the waiting state.

      Step 6. Exit.

Code:-

#include<stdio.h>
int queue[20];
int front=-1;
int rear=-1;

// function for insert the element into queue
void insert(int a)
{
if(front==-1)
front=0;
rear++;
queue[rear]=a;
}

// function for delete the element from the queue
int delete()
{
int a;
if(front==-1 && front>rear)
return 0;
else
{
a=queue[front];
front=front+1;
return a;
}
}

// Driver function
int main()
{
int graph[10][10],n,visited[10]={0},ans[10],i,j,k=0;
printf(“Enter number of vertex n”);
scanf(“%d”,&n);
printf(“Enter the graph in adjacency form n”);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
scanf(“%d”,&graph[i][j]);
}
i=1;
while(i!=0)
{
int flag=0;
if(visited[i]==0)
{
ans[k]=i;
k++;
}
visited[i]=1;
for(j=1;j<=n;j++)
{
if(visited[i]!=0)
{
if(graph[i][j]!=0)
{
flag=1;
// if vertex is not visited then insert it into queue
if(visited[j]==0)
insert(j);
}
}
}
// if there is no any child of the vertex
if(flag==0)
{
j=1;
while(1)
{
j++;
if(graph[j][i]==1)
{
insert(j);
break;
}
}
}
i=delete();
}
// printing of answer
printf(“Traversal is:-n”);
for(i=0;i<k;i++)
printf(“%d “,ans[i]);
return 0;
}

Output:-

Enter number of vertex
6
Enter the graph in adjacenccy form
0 0 0 0 0 0
1 0 0 1 0 0
0 1 0 0 0 1
1 0 0 0 0 0
0 1 0 0 1 0
Traversal is:-
1 2 4 3 5 6



Leave a Reply

Your email address will not be published.