dsdeep

BFS

Sep 14th, 2021
1,095
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <fstream>
  3. #include <vector>
  4. #include <numeric>
  5. #include <set>
  6. #include <queue>
  7. using namespace std;
  8.  
  9. void bfs(queue<int> myQueue,vector<int> vecData[],vector<bool> visited,vector<int> parent,vector<int> distance){
  10.     if(myQueue.empty())return;
  11.     int currentElement = myQueue.front();
  12.     visited[currentElement] = true;
  13.     myQueue.pop();
  14.     cout << "Visited " << currentElement << ", Distance " << distance[currentElement] <<", Parent " << parent[currentElement] << endl;
  15.     for(int i=0;i<vecData[currentElement].size();i++){
  16.         int data = vecData[currentElement][i];
  17.         if(!visited[data]){
  18.             distance[data] = distance[currentElement]+1;
  19.             parent[data] = currentElement;
  20.             myQueue.push(data);
  21.         }
  22.     }
  23.     bfs(myQueue,vecData,visited,parent,distance);
  24.  
  25. }
  26.  
  27. int main(){
  28.  
  29.     ifstream in;
  30.     in.open("/home/deep/Study/CPP/Lab/dfs-data.txt");
  31.     int m,data1,data2;
  32.     in >> m;
  33.     set<int> pureData;
  34.    
  35.     int p = 0;
  36.     while(in >> data1 && in >> data2){
  37.         pureData.insert(data1);
  38.         pureData.insert(data2);
  39.         p++;
  40.     }  
  41.     int n = *pureData.rbegin()+1;
  42.     vector<int> vecData[n];
  43.     vector<bool> visited(n,false);
  44.     vector<int>parent(n,0);
  45.     vector<int> distance(n,0);
  46.  
  47.     in.clear();
  48.     in.seekg(1);
  49.     while(in >> data1 && in >> data2){
  50.         vecData[data1].push_back(data2);
  51.         vecData[data2].push_back(data1);
  52.     }
  53.    
  54.     in.close();
  55.  
  56.     cout << "\n\t     BFS\n" << endl;
  57.  
  58.     queue<int> myQueue;
  59.     myQueue.push(*pureData.begin());
  60.     bfs(myQueue,vecData,visited,parent,distance);
  61.     cout << endl;
  62.  
  63.     return 0;
  64. }
RAW Paste Data