BFS

#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<list>
#include<queue>

using namespace std;

int v;
int matrix[100][100],clr[100],dis[100],prev[100];
void BFS(int s);

int main()

{
    int r,c,n,s;
    int edge=1;
    cout<<"Input no of Vertex : "<<endl;
    cin>>v;

    do
    {
        cout<<"Edge "<<edge<<": "<<endl;
        cin>>r>>c;
        if(r>v || c>v)
        {
            cout<<"Invalid Input,Try Again"<<endl;
        }

        else
        {
            matrix[r][c]=1;
            matrix[c][r]=1;
            edge++;
        }

    }
    while(r!=0 || c!=0);

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

if(s<1 || s>v){
    cout<<"Invalid"<<endl;
}
else
{
     BFS(s);
}

    cout<<endl<<"Vertex no: "<<endl;
    for(int g=1; g<=v; g++){
        cout<<g<<endl;
    }
    cout<<endl<<"Colour: "<<endl;
    for(int h=1; h<=v; h++){
        cout<<clr[h]<<" ";
    }
    cout<<endl<<"Distance: "<<endl;
    for(int m=1; m<=v; m++){
        cout<<dis[m]<<" ";
    }
    cout<<endl<<"Previous: "<<endl;
    for(int n=1; n<=v; n++){
        cout<<prev[n]<<" ";
    }

  return 0;

}




void BFS(int s)
{
    queue<int> Q;
    int i,j,u;
    //int clr[100],dis[100],prev[100];
    for(i=1; i<=v; i++)
    {
        clr[i]=0;
        dis[i]=1500000000;
        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;
}

}