Wednesday, 3 February 2016

Breadth First Search (BFS)

#include<bits/stdc++.h>
using namespace std;
int main()
{
    vector<int>nodes[1000];
    int i,j,edges,a,b;
    cin>>edges;
    for(i=0;i<edges;i++)
    {
        cin>>a>>b;
        nodes[a].push_back(b);//INSERTING ELEMENTS
        nodes[b].push_back(a);
    }
    for(i=0;i<100;i++)
    {
        if(!nodes[i].empty())
        {
            cout<<"("<<i<<") : ";
            for(vector<int>::iterator it=nodes[i].begin();it!=nodes[i].end();++it)//ITERATOR TRAVERSES ALL ELEMENTS UNDER A NODE
            {
                cout<<*it<<" ";
            }
            cout<<endl;
        }
    }
    queue<int>q;
    bool visited[1000];
    int start,level[1000],parent[1000];
    cin>>start;//STARTING NODE
    memset(visited,0,sizeof(visited));
    visited[start]=1;//STARTING NODE IS ALREADY VISITED WHEN TAKEN AS INPUT
    q.push(start);
    level[start]=0;//LEVEL OF STARTING NODE IS ZERO
    while(!q.empty())
    {
        int front=q.front();
        cout<<front<<" ";
        for(vector<int>::iterator it=nodes[front].begin();it!=nodes[front].end();++it)
        {
            if(!visited[*it])
            {
                visited[*it]=1;//VISITING ALL ELEMENTS OF A NODE
                level[*it]=level[front]+1;//INCREASING 1 LEVEL FROM PARENT NODE
                parent[*it]=front;//PUTTING NEXT NEARING NODE OF PARENT AS PARENT
                q.push(*it);//INSERTING NODES IN THE QUEUE
            }
        }
        q.pop();//DELETING CURRENT FRONT PARENT NODE AND INITIALINZE THE NEXT NODE AS PARENT
    }
    return 0;

}

No comments:

Post a Comment