Advertisement
MasterAler

graph breadth walk

Feb 11th, 2019
98
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.85 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <sstream>
  5. #include <list>
  6.  
  7. using namespace std;
  8. typedef vector<vector<int>> GraphType;
  9.  
  10. list<size_t> get_neighbours(const GraphType& graph, const vector<bool>& visits, size_t target)
  11. {
  12.     list<size_t> result;
  13.  
  14.     for (size_t i = 0; i < graph.size(); ++i)
  15.     {
  16.         if (0 != graph[target][i] && !visits[i])
  17.             result.push_back(i);
  18.     }
  19.  
  20.     return result;
  21. }
  22.  
  23. void walk_some_vertice(const GraphType& graph, vector<bool>& visits, size_t target)
  24. {
  25.     visits[target] = true;
  26.     cout << "We are at node: " << target << endl;
  27.  
  28.     list<size_t> neighbours = get_neighbours(graph, visits, target);
  29.     while(!neighbours.empty())
  30.     {
  31.         size_t new_target = neighbours.front();
  32.         visits[new_target] = true;
  33.         cout << "We are at node: " << new_target << endl;
  34.  
  35.         neighbours.splice(end(neighbours), get_neighbours(graph, visits, new_target));
  36.         neighbours.pop_front();
  37.     }
  38. }
  39.  
  40. void breadth_walk(const GraphType& graph)
  41. {
  42.     vector<bool> visited(graph.size(), false);
  43.  
  44.     for(size_t i = 0; i < graph.size(); ++i)
  45.     {
  46.         if (!visited[i])
  47.             walk_some_vertice(graph, visited, i);
  48.     }
  49. }
  50.  
  51. int main()
  52. {
  53.     GraphType graph;
  54.  
  55.     unsigned N;
  56.     cin >> N;
  57.  
  58.     graph.resize(N, vector<int>(N, 0));
  59.  
  60.     string line;
  61.     getline(cin, line);
  62.  
  63.     for (unsigned i = 0; i < N; ++i)
  64.     {
  65.         getline(cin, line);
  66.         stringstream x(line);
  67.  
  68.         size_t neighbour;
  69.         while (x >> neighbour)
  70.         {
  71.             graph[i][neighbour] = 1;
  72.             graph[neighbour][i] = 1;
  73.         }
  74.  
  75.         graph[i][i] = 0;
  76.     }
  77.  
  78.     for(auto line : graph)
  79.     {
  80.         for(int val: line)
  81.             cout << val << '\t';
  82.         cout << endl;
  83.     }
  84.  
  85.     breadth_walk(graph);
  86.  
  87.     return 0;
  88. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement