Implementation Of BFS

Here is the implementation of Breadth First Search in C++ , which we discussed in the last post.
As,we said in last post, BFS is used to calculate the shortest distance, the distance matrix here actually takes care of that.

/*
BFS: The output may change depending on the order of input given
     But the structure of graph remains same, i.e irrespective
     of the order of given vertices, the distances computed remains same.
     dis[MAX] --> is used to calculate distances of
                  nodes from the source vertex.
     vertices count starting from 1 to N.
     it uses adjacency list representation (with the help of vectors);
*/

#define NIL -1
#define white 0
#define gray 1
#define black 2
using namespace std;

int dis[MAX];
int parent[MAX];
int color[MAX];
vector<int> g[MAX];

void BFS(int s,int v)
{
    int len,x,k;
    queue<int> Q;
    parent[s]=NIL;
    dis[s]=0;
    color[s]=gray;

    Q.push(s);
    while(!Q.empty())
    {
        x=Q.front();
        Q.pop();
        len=g[x].size();
        for(int i=0;i<len;i++)
            if(g[x][i] && color[g[x][i]]==white)
            {
                k=g[x][i];
                color[k]=gray;
                dis[k]=dis[x]+1;
                parent[k]=x;
                Q.push(k);
            }
        color[x]=black;
        printf("%d ",x);
    }

    printf("\n***distances***\n");
    for(int i=1;i<=v;i++)
     printf("distance[%d]= %d\n",i,dis[i]);
    return;
}

int main()
{
    int v,e,s,d;
    printf("Enter no of vertices: ");
    scanf("%d",&v);
    printf("Enter no of edges: ");
    scanf("%d",&e);
    for(int i=1;i<=e;i++)
    {
        printf("Enter source and destination: ");
        scanf("%d %d",&s,&d);
        g[s].push_back(d);
        g[d].push_back(s);
    }
    printf("Enter source of graph: ");
    scanf("%d",&s);
    BFS(s,v);
    return 0;
}

Check the BFS, on the graph discussed in the previous post, and verify the distance matrix to get an idea of structure of the graph.!

About these ads

2 comments

  1. trunks175 · · Reply

    Superb :)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 33 other followers

%d bloggers like this: