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