BFS

#include <iostream>
#include<queue>

using namespace std;

int v;
int matrix[100][100];
void BFS(int s);

int main ()
{
    int  r, c, n, s;
    int edge = 1;

    cout<<"Input no of vertices: ";
    cin>>v;

    do{
        cout<<"Edge "<<edge<<": ";
        cin>>r>>c;
         if(r>v || c>v)
            cout<<"Invalid input"<<endl;
        else{
            matrix[r][c] = 1;
            matrix[c][r] = 1;
            edge++;
        }
    }while(r != 0 && c!=0);

    cout<<"Enter the source node : ";
    cin>>s;

    BFS(s);

    return 0;
}

void BFS (int s)
{
    queue <int> Q;
    int i,j,u;
    int clr[100], dis[100], prev[100];

    for(i=0; i<=v; i++)
    {
        clr[i] = 0;
        dis[i] = 200000000;
        prev[i] = -1;
    }

    clr[s] = 1;
    dis[s] = 0;
    Q.push(s);

    while(!Q.empty())
    {
        u = Q.front();
        Q.pop();

        for(i=1; i<=v; i++)
        {
            if(matrix[u][i] == 1 && clr[i] == 0)
            {
                clr[i] = 1;
                dis[i] = dis[u] + 1;
                prev[i] = u;
                Q.push(i);
            }
        }
        clr[u] = 2;
    }
    cout<<endl<<"vertex no  : ";
    for(i=1; i<=v; i++)
        cout<<i<<" ";
    cout<<endl<<"colour     : ";
    for(i=1; i<=v; i++)
        cout<<clr[i]<<" ";
    cout<<endl<<"distance   : ";
    for(i=1; i<=v; i++)
        cout<<dis[i]<<" ";
    cout<<endl<<"previous   : ";
    for(i=1; i<=v; i++)
        cout<<prev[i]<<" ";
}