Friday 14 November 2014

Breadth first search in a Graph

struct queue//to store all adjacent nodes
{
    int d[100];
    int front,rear;
}s;
main()
{
int k;
printf("Enter the total number of nodes you want to insert\n");
scanf("%d",&k);
int a[k][k];//adjacency matric
int visit[k];//Array to keep track of node visited
int i;
for(i=0;i<k;i++)
    visit[i]=0;
int j;
for(i=0;i<k;i++)
    for(j=0;j<k;j++)
{
    printf("Is node %d connected to node %d",i+1,j+1);//Enter 1 if connected else 0
    scanf("%d",&a[i][j]);
}
s.front=-1;
s.rear=-1;
printf("Enter the starting node\n ");
int start;
scanf("%d",&start);
start--;
s.d[0]=start;
visit[start]=1;
s.front++;s.rear++;
do//Loop performing queue operations
{
int disp=s.d[s.front];
printf("%d\n",disp+1);
int counter=0;
for(i=0;i<k;i++)
{
    if(a[disp][i]==1&&visit[i]==0)
    {
        s.d[++s.rear]=i;
    counter++;
    visit[i]++;
    }
}
{s.front++;}
}while(s.front<=s.rear);
}

No comments:

Post a Comment