dsdeep

DFS

Sep 14th, 2021
1,151
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. using namespace std;
  7.  
  8. void dfs(int startNode,int parent, vector<int> myVec[], vector<bool>* visited,vector<int>* savedPath){
  9.     savedPath->push_back(startNode);
  10.     cout << "Visited " << startNode  <<", Parent " << parent << endl;
  11.     visited->at(startNode) = true;
  12.     for(int i=0;i<myVec[startNode].size();i++){
  13.         int posValue = myVec[startNode][i];
  14.         if(!visited->at(posValue)) dfs(posValue,startNode,myVec,visited,savedPath);
  15.     }
  16. }
  17.  
  18.  
  19. int main(){
  20.  
  21.     ifstream in;
  22.     in.open("/home/deep/Study/CPP/Lab/dfs-data.txt");
  23.     int m,data1,data2;
  24.     in >> m;
  25.     set<int> pureData;
  26.    
  27.     int p = 0;
  28.     while(in >> data1 && in >> data2){
  29.         pureData.insert(data1);
  30.         pureData.insert(data2);
  31.         p++;
  32.     }
  33.      
  34.     int n = *pureData.rbegin()+1;
  35.     vector<int> vecData[n];
  36.     vector<bool> visited(n,false);
  37.     vector<int> savedPath;
  38.  
  39.     in.clear();
  40.     in.seekg(1);
  41.     while(in >> data1 && in >> data2){
  42.         vecData[data1].push_back(data2);
  43.         vecData[data2].push_back(data1);
  44.     }
  45.    
  46.     in.close();
  47.     cout << "\n\tDFS\n" << endl;
  48.     for(int i=0;i<pureData.size();i++){
  49.         if(accumulate(visited.begin(),visited.end(),0) == pureData.size()) break;
  50.         auto it = pureData.begin();
  51.         advance(it,i);
  52.         dfs(*it,*it,vecData,&visited,&savedPath);
  53.     }
  54.     cout << endl;
  55.     return 0;
  56. }
RAW Paste Data