Advertisement
AshfaqFardin

Graph - BFS Algorithm

Aug 22nd, 2021
957
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.88 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int N = 1e5+2; //infinity
  6. bool visited[N] = {false};
  7. vector<int> adj[N];
  8.  
  9. int main()
  10. {
  11.     int numNodes; cin >> numNodes;
  12.     int numEdges; cin >> numEdges;
  13.    
  14.     int edgeA, edgeB;
  15.     for(int i = 0; i < numEdges; i++){
  16.         cin >> edgeA;
  17.         cin >> edgeB;
  18.        
  19.         adj[edgeA].push_back(edgeB);
  20.         adj[edgeB].push_back(edgeA);
  21.     }
  22.    
  23.     queue<int> que;
  24.     que.push(1);
  25.     visited[1] = true;
  26.    
  27.     while(!que.empty()){
  28.         int node = que.front();
  29.        
  30.         que.pop();
  31.         cout << node << endl;
  32.        
  33.         vector<int> :: iterator it;
  34.         for(it = adj[node].begin(); it != adj[node].end(); it++){
  35.             if(!visited[*it]){
  36.                 visited[*it] = true;
  37.                 que.push(*it);
  38.             }
  39.         }
  40.     }
  41.    
  42.     return 0;
  43. }
  44.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement