Sunjaree

BFS

Oct 24th, 2020 (edited)
693
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using  namespace  std;
  3.  
  4. #define endl     "\n"
  5. #define ll       long long
  6. #define PI       acos(-1.0)
  7. #define test     cout<<"\n****\n"
  8. #define LCM(a,b) ((a/__gcd(a,b))*b)
  9. #define precise  fixed(cout);cout<<setprecision(12)
  10. #define fast     ios_base :: sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
  11.  
  12.  
  13. #define MAX 100
  14. vector<int> graph[MAX+10];
  15. int distan[MAX+10];
  16.  
  17. void BFS(int root,int numNode){
  18.  
  19.     memset(distan,-1,sizeof(distan));
  20.     distan[root] = 0;
  21.  
  22.     queue<int> que;
  23.     que.push(root);
  24.  
  25.     while (!que.empty()){
  26.  
  27.         int parent = que.front();
  28.         que.pop();
  29.         for (int i=0;i<graph[parent].size();i++) {
  30.             int child = graph[parent][i];
  31.             if (distan[child]==-1){
  32.                 distan[child] = distan[parent] + 1;
  33.                 que.push(child);
  34.             }
  35.         }
  36.     }
  37.  
  38.     for(int i=1;i<=numNode;i++){
  39.         cout<<i<<"->"<<distan[i]<<endl;
  40.     }
  41.  
  42. }
  43.  
  44. void ConnectedAmong(int numNode){
  45.  
  46.     for(int i=1;i<=numNode;i++){
  47.         cout<<i<<"->";
  48.         if(graph[i].size()==0){
  49.  
  50.             cout<<"NULL";
  51.         } else {
  52.             for (int j = 0; j < graph[i].size(); j++) {
  53.                 cout << graph[i][j] << " ";
  54.             }
  55.         }
  56.         cout<<endl;
  57.     }
  58. }
  59.  
  60. int main(){
  61.  
  62.     int numNode,numEdge;
  63.     cin>>numNode>>numEdge;
  64.  
  65.     for(int i=0;i<numEdge;i++){
  66.         int node,edge;
  67.         cin>>node>>edge;
  68.         graph[node].push_back(edge);
  69.     }
  70.  
  71.     cout<<"The graph is Connected among: \n";
  72.     ConnectedAmong(numNode);
  73.     cout<<endl;
  74.  
  75.     cout<<"Enter the root of your graph: ";
  76.     int root;
  77.     cin>>root;
  78.     cout<<endl;
  79.     cout<<"Distance of every node from root: \n";
  80.     BFS(root,numNode);
  81.  
  82. }
  83.  
  84.  
  85. *************************************************************************************
  86. **************************************NSUPS******************************************
  87. #include<bits/stdc++.h>
  88. using  namespace  std;
  89.  
  90. #define endl     "\n"
  91. #define ll       long long
  92. #define PI       acos(-1.0)
  93. #define test     cout<<"\n****\n"
  94. #define LCM(a,b) ((a/__gcd(a,b))*b)
  95. #define precise  fixed(cout);cout<<setprecision(20)
  96. #define fast     ios_base :: sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
  97.  
  98. const int N = 100;
  99. vector <int> graph[ N ];
  100. int dist[ N ]; // dist of every node from the source
  101. void bfs(int source) {
  102.     memset(dist, -1, sizeof(dist));
  103.     queue <int> q;
  104.     dist[source] = 0;
  105.     q.push(source);
  106.     while (!q.empty()) {
  107.         int f = q.front();
  108.         q.pop();
  109.         for (int i = 0; i < graph[f].size(); i++) {
  110.             int child = graph[f][i];
  111.             if (dist[child] == -1) {
  112.                 dist[child] = dist[f] + 1;
  113.                 q.push(child);
  114.             }
  115.         }
  116.     }
  117.     for (int i = 1; i <= 10; i++) cout << dist[i] << endl;
  118. }
  119. int main() {
  120.  
  121.     graph[1].push_back(2);
  122.     graph[1].push_back(4);
  123.     graph[1].push_back(3);
  124.     graph[2].push_back(6);
  125.     graph[4].push_back(7);
  126.     graph[3].push_back(7);
  127.     graph[3].push_back(8);
  128.     graph[6].push_back(10);
  129.     graph[8].push_back(7);
  130.     graph[7].push_back(9);
  131.     graph[8].push_back(5);
  132.     graph[10].push_back(9);
  133.     graph[10].push_back(5);
  134.  
  135.     bfs(1);
  136.     return 0;
  137. }
RAW Paste Data