Like us on google+

Wednesday, 21 May 2014

Widgets

Breadth First Search( BFS)

#include<stdio.h>
#define max 10
int main()
{
int a[max][max];
int visit[max]={0};
int f=0,r=0;
int i,j,n,src,u;
int q[max];
int fl;

printf("Enter the number of vertices\n");
    scanf("%d",&n);

    printf("Enter the adj matrix\n");

    for(i = 1 ; i <= n ; i++)
    {
        for(j = 1 ; j <= n ; j++)
        {
            scanf("%d",&a[i][j]);
        }
    }

    printf("Enter the source\n");
    scanf("%d",&src);

    visit[src]=1;
    q[r]=src;

    while(f<=r)
    {
    u=q[f];  //pop from queue
    f+=1;    // incr front
    for(i = 1 ; i <= n ; i++)
        {
            if(!visit[i] && a[u][i])
            {
                visit[i] = 1;
                printf("%d-%d\n",u,i);
                r = r + 1;
                q[r] = i;
            }
        }

    }

    for(i = 1 ; i <= n ; i++)
    {
        if(visit[i] == 0)
        {
            fl = 1;
        }
    }

    if(fl == 0)
    {
        printf("Connected graph\n");
    }
    else
    {
        printf("disconnected graph\n");
    }

    return 0;


}

----------------------------------------------------------------------------------------------------------------------
OUTPUT:
Enter the number of vertices
4
Enter the adj matrix
0 1 1 1
1 0 1 0
1 1 0 0
1 0 0 0
Enter the source
1
1-2
1-3
1-4
Connected graph

SHARE THIS POST   

  • Facebook
  • Twitter
  • Myspace
  • Google Buzz
  • Reddit
  • Stumnleupon
  • Delicious
  • Digg
  • Technorati
About us:
Hi guys Sandesh and Rajesh here ... studing engineering in PESIT started this blog as a google contest and also we love blogging ...Hope u like it ...Encourage us by liking us on g+... Any queries dont hesitate to ask Read More →

0 comments: