Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<bits/stdc++.h>
- #include<Queue>
- using namespace std;
- int v,i,j,a,b,k=1,s;
- int p[100],d[2000000],clr[100];
- int adj[100][100],u;
- void BFS(int s)
- {
- for(i=1;i<=v;i++)
- {
- clr[i]=0;
- p[i]=-1;
- d[i]=0;
- }
- clr[s]=1;
- //p[s]=-1;
- queue<int> Q;
- Q.push(s);
- while(!Q.empty()){
- u=Q.front();
- Q.pop();
- for(i=1;i<=v;i++)
- {
- if(adj[u][i]==1 && clr[i]==0)
- {
- clr[i]=1;
- d[i]=d[u]+1;
- p[i]=u;
- Q.push(i);
- }
- }
- clr[u]=2;
- }
- cout<<"previous"<<endl;
- for(i=1;i<=v;i++)
- {
- cout<<p[i]<<" ";
- }
- cout<<endl;
- cout<<"cost"<<endl;
- for(i=1;i<=v;i++)
- {
- cout<<d[i]<<" ";
- }
- cout<<endl;
- cout<<"color"<<endl;
- for(i=1;i<=v;i++)
- {
- cout<<clr[i]<<" ";
- }
- }
- int main()
- {
- cout<<"vertex: ";
- cin>>v;
- do{
- cout<<"Edge"<<k<<":";
- cin>> a >> b ;
- cout<<endl;
- if(a>v+1 || b>v+1)
- {
- cout<<"Input is invalid"<<endl;
- }
- else{
- adj[a][b]=1;
- adj[b][a]=1;
- }
- k++;
- }while(a!=0 && b!=0);
- for(i=1;i<=v;i++){
- int count=0;
- for(j=1;j<=v;j++)
- {
- cout<<adj[i][j]<<" ";
- }
- cout<<endl;
- }
- cout<<"Enter source node"<<endl;
- cin>>s;
- if(s>v || s< 1)
- cout<<"invalid input"<<endl;
- else
- BFS(s);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement