fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. vector< vector<int> > G(101);
  5. vector<int> dis(101, -1);
  6. vector<int> color(101, -1);
  7.  
  8. void inputList(int n, int e);
  9. void BFS(int s);
  10. void printDistance(int n);
  11.  
  12. int main()
  13. {
  14.     int nodes, edges, i, source;
  15.     cout<<"Enter total number of nodes and edges:"<<endl;
  16.     cin>>nodes>>edges;
  17.     inputList(nodes, edges);
  18.     cout<<"Enter source: ";
  19.     cin>> source;
  20.     cout<<"Distance of each node before BFS"<<endl;
  21.     printDistance(nodes);
  22.     BFS(source); ///----
  23.     cout<<"Distance of each node After BFS"<<endl;
  24.     printDistance(nodes);
  25.  
  26. }
  27. void inputList(int n, int e)
  28. {
  29.     int i, u, v;
  30.     cout<<"Enter the edges:"<<endl;
  31.     for(i=0; i<e; i++){
  32.         cin>>u>>v;
  33.         G[u].push_back(v);
  34.         G[v].push_back(u);
  35.     }
  36.     cout<<"Input Complete....."<<endl;
  37. }
  38. void BFS(int s)
  39. {
  40.     int u, v, i;
  41.     queue<int> Q;
  42.     Q.push(s); /// enqueue source node
  43.     color[s] = 0;
  44.     dis[s] = 0;
  45.     while(!Q.empty())
  46.     {
  47.         u = Q.front();
  48.         Q.pop();
  49.         color[u]=1;
  50.         for(i=0; i<G[u].size(); i++){
  51.             v = G[u][i];
  52.             if(color[v]==-1){
  53.                 Q.push(v);
  54.                 color[v]=0;
  55.                 dis[v] = dis[u]+1;
  56.             }
  57.         }
  58.     }
  59. }
  60.  
  61. void printDistance(int n)
  62. {
  63.     for(int i =1; i<=n; i++){
  64.         cout<<"Distance of node "<<i<< " is " <<dis[i]<<endl;
  65.     }
  66. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
7 8
1 2
1 4
1 5
2 3
2 6
3 7
4 5
6 7

2
stdout
copy 
Enter total number of nodes and edges:
Enter the edges:
Input Complete.....
Enter source: Distance of each node before BFS
Distance of node 1 is -1
Distance of node 2 is -1
Distance of node 3 is -1
Distance of node 4 is -1
Distance of node 5 is -1
Distance of node 6 is -1
Distance of node 7 is -1
Distance of each node After BFS
Distance of node 1 is 1
Distance of node 2 is 0
Distance of node 3 is 1
Distance of node 4 is 2
Distance of node 5 is 2
Distance of node 6 is 1
Distance of node 7 is 2
https://ideone.com/rKiGTc
language:
C++14 (clang 8.0)
created:
2 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!