Facebook
From Sweltering Panda, 4 Years ago, written in C++.
Embed
Download Paste or View Raw
Hits: 351
  1. //
  2. // Created by rafalbyczek on 13.06.16.
  3. //
  4.  
  5. #ifndef ZADANIE_K_BFS_BFS_H
  6. #define ZADANIE_K_BFS_BFS_H
  7.  
  8. #include <queue>
  9. #include <string>
  10. #include <set>
  11.  
  12. using namespace std;
  13.  
  14. template<typename T, typename S, typename U, typename V>
  15. void bfs(T begin, T end, S comp, U sasiad, V akcja) {
  16.     auto a = *begin;
  17.     queue <decltype(a)> Q;
  18.     set<decltype(a), decltype(comp)> A(comp);
  19.     typename set<decltype(a), decltype(comp)>::iterator f;
  20.  
  21.     for (auto it = begin; it != end; it++) {
  22.         Q.push(*it);
  23.     }
  24.  
  25.     while(!Q.empty()) {
  26.         auto x = Q.front();
  27.         Q.pop();
  28.  
  29.         for(auto it = sasiad(x).first; it != sasiad(x).second; it++) {
  30.             auto a = *it;
  31.             f = A.find(a);
  32.  
  33.             if(f == A.end()) {
  34.                 A.insert(a);
  35.                 akcja(a);
  36.                 Q.push(a);
  37.             }
  38.         }
  39.     }
  40. }
  41.  
  42. #endif //ZADANIE_K_BFS_BFS_H