Breadth First Search (BFS)

Aim: Implement Breadth first Search(BFS) non recursively itself

Program:

#include<stdio.h>

int visited[10],st,q[10],v,i,j,am[10][10],n,front=0,rear=0;

void main()

{

clrscr();

printf("enter number of vertices");

scanf("%d",&n);

printf("enter adjacent matrix");

for(i=1;i<=n;i++)

{

for(j=1;j<=n;j++)

scanf("%d",&am[i][j]);

visited[i]=0;

}

printf("enter source node");

scanf("%d",&st);

bfs(st);

getch();

}

int bfs(int st)

{

q[rear]=st;

rear++;

while(front<rear)

{

v=q[front];

front++;

if(visited[v]==0)

{

visited[v]=1;

printf("-->%d",v);

}

for(i=1;i<=n;i++)

{

if(am[v][i]==1 && visited[i]==0)

{

if(inqueue(i)==0)

{

q[rear]=i;

rear++;

}

}

}

}

}

int inqueue(int n)

{

int j;

for(j=front;j<rear;j++)

{

if(q[j]==n)

return  1;

}

return 0;

}

input:

  input is given in the adjacent matrix for the below graph

output :