Thursday, April 19, 2012

Breadth First Search(BFS) in C++


#include<iostream>

using namespace std;

int n;


struct vertex
{
    int index;
    int no_edges;
    int adj[20];
    int predecessor;
    int d;
    char color;

}v[20];

struct queue{

    int data;
    queue * link;

}*front, *rear;



void enqueue(int e)
{
    queue * ptr;
    ptr = new queue;
    (*ptr).link = NULL;
    (*ptr).data = e;
    if(rear == NULL)
    {

        front = rear = ptr;
    }
    else
    {
        (*rear).link = ptr;
        rear = ptr;
    }
}



int dequeue()
{
    queue * temp;
    int e;
    if(front == NULL)
        return 0;
    else if((*front).link == NULL)
    {
        e = (*front).data;
        temp = front;
        front  = rear = NULL;
        delete temp;

    }
    else{
        e = (*front).data;
        temp = front;
        front = (*front).link;
        delete temp;
    }
    return e;

}

void BFS(vertex s);



int main()
{
    front = NULL;
    rear = NULL;
    int i,j, noe,u, u2;



    cout<<"Enter the number of edges :";
    cin>>n;

    cout<<"Let the vertices be : ";
    for(i = 1;i<=n;i++)
        cout<<i<<" ";
    cout<<"\n";

    for(i = 1;i<=n;i++)
    {
        v[i].index = i;
        cout<<"Enter the number of adjacent vertices for vertex no : "<<i<<" : ";
        cin>>v[i].no_edges;
        if(v[i].no_edges != 0)
            cout<<"Enter the adjacent vertices : ";
        for(j = 1;j<=v[i].no_edges;j++)
            cin>>v[i].adj[j];
    }

    cout<<"Enter a vertex no : ";
    cin>>u;
    BFS(v[u]);

    cout<<"Enter another vertex no :";
    cin>>u2;

    cout<<"\nDistance : "<< v[u2].d;


    if(  v[u2].d > 50   )
        cout<<"Points ureachable...";
    else
    {
        cout<<"Path : "<<u2;
        i = v[u2].predecessor;
        while(i != 0)
        {
                cout<<" -> "<<i;
                i = v[i].predecessor;
        }
    }


    return 0;
}


void BFS(vertex s)
{
    int u,i,j,noe,k;
    for(i = 1; i<=n ;i++)
    {

        v[i].color = 'w';
        v[i].predecessor = 0;
        v[i].d = 100;

    }
        v[s.index].color = 'g';
        v[s.index].predecessor = 0;
        v[s.index].d = 0;

    enqueue(s.index);
    while(front)
    {
        u = dequeue();
        noe = v[u].no_edges;
        for(j = 1;j<=noe;j++)
        {
            k = v[u].adj[j];
            if (v[k].color == 'w')
            {
                v[k].color = 'g';
                v[k].d = v[u].d + 1;
                v[k].predecessor = u;
                enqueue(k);
            }
            v[u].color = 'b';

        }



    }


}





No comments:

Post a Comment