SHARE
TWEET

Graph

arsovski Jan 21st, 2020 65 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<iostream>
  2. #include<vector>
  3. #include<list>
  4. #include <queue>
  5. // INPUTS:
  6. //    7
  7. //    8
  8. //    
  9. //    0 1 1
  10. //    1 1 2
  11. //    0 1 2
  12. //    1 1 3
  13. //    2 1 4
  14. //    3 1 4
  15. //    4 1 5
  16. //    5 1 6
  17.  
  18. struct Vertex
  19. {
  20.     int weight;
  21.     int vertex_number;
  22.  
  23.     Vertex(int weight, int vertex_number)
  24.     {
  25.         this->weight = weight;
  26.         this->vertex_number = vertex_number;
  27.     }
  28. };
  29.  
  30.  
  31. //undirected weight graph
  32. std::vector<std::list<Vertex>> graph;
  33.  
  34. //TODO make bfs and dfs
  35.  
  36. bool connection_exists(int from, int to)
  37. {
  38.     for (auto element : graph[from])
  39.     {
  40.         if (element.vertex_number == to)
  41.         {
  42.             return true;
  43.         }
  44.     }
  45.  
  46.     return false;
  47. }
  48.  
  49. void add_connection(int from, int weight, int to)
  50. {
  51.     if (!connection_exists(from, to))
  52.     {
  53.         graph[from].push_back({weight, to});
  54.         graph[to].push_back({weight, from});
  55.     }
  56. }
  57.  
  58. void print_graph()
  59. {
  60.     for (int i = 0; i < graph.size(); i++)
  61.     {
  62.         std::cout << "Vertex " << i << ": ";
  63.  
  64.         for (auto element : graph[i])
  65.         {
  66.             std::cout << element.vertex_number << "->" << element.weight << " ";
  67.         }
  68.  
  69.         std::cout << std::endl;
  70.     }
  71. }
  72.  
  73.  
  74. std::vector<bool> visited;
  75.  
  76. void bfs(int from)
  77. {
  78.     std::queue<int> next_to_process;
  79.     next_to_process.push(from);
  80.  
  81.     while (!next_to_process.empty())
  82.     {
  83.         int next_index = next_to_process.front();
  84.         next_to_process.pop();
  85.         visited[next_index] = true;
  86.  
  87.         std::cout << next_index << " ";
  88.  
  89.         for (auto neighbor : graph[next_index])
  90.         {
  91.             if (!visited[neighbor.vertex_number])
  92.             {
  93.                 visited[neighbor.vertex_number] = true;
  94.                 next_to_process.push(neighbor.vertex_number);
  95.             }
  96.         }
  97.     }
  98.  
  99.     std::cout << std::endl;
  100. }
  101.  
  102.  
  103. std::vector<bool> visited_dfs;
  104.  
  105. void dfs(int from)
  106. {
  107.     std::cout << from << " ";
  108.     visited_dfs[from] = true;
  109.  
  110.     for (auto neighbor : graph[from])
  111.     {
  112.         if (!visited_dfs[neighbor.vertex_number])
  113.         {
  114.             visited_dfs[neighbor.vertex_number] = true;
  115.             dfs(neighbor.vertex_number);
  116.         }
  117.     }
  118. }
  119.  
  120. std::vector<bool> visited_topo;
  121. std::list<int>  ordered_nodes;
  122.  
  123. //DFS na svi nodes
  124. void _recursive_topological(int from)
  125. {
  126.     visited_topo[from] = true;
  127.  
  128.     //go through neighbors
  129.     for(auto element: graph[from])
  130.     {
  131.         if(!visited_topo[element.vertex_number])
  132.         {
  133.             visited_topo[element.vertex_number] = true;
  134.             _recursive_topological(element.vertex_number);
  135.         }
  136.     }
  137.  
  138.  
  139.     ordered_nodes.push_back(from);
  140.  
  141.  
  142. }
  143.  
  144. void topological_sort()
  145. {
  146.     for(int i=0; i < graph.size();i++)
  147.     {
  148.         if(!visited_topo[i])
  149.             _recursive_topological(i);
  150.     }
  151.  
  152.     ordered_nodes.reverse();
  153.  
  154.     for(auto element : ordered_nodes)
  155.     {
  156.         std::cout << element << " ";
  157.     }
  158.  
  159.     std::cout << std::endl;
  160.  
  161. }
  162.  
  163.  
  164. int main()
  165. {
  166.     int nodes, edges;
  167.     std::cin >> nodes >> edges;
  168.  
  169.     graph.resize(nodes);
  170.     visited_dfs.resize(nodes, false);
  171.     visited.resize(nodes, false);
  172.     visited_topo.resize(nodes, false);
  173.     for (int i = 0; i < edges; i++)
  174.     {
  175.         int from, weight, to;
  176.         std::cin >> from >> weight >> to;
  177.         add_connection(from, weight, to);
  178.     }
  179.  
  180.  
  181.     //print_graph();
  182.  
  183.     //dfs(6);
  184.     std::cout << std::endl;
  185.  
  186.     //bfs(6);
  187.  
  188.     //TODO topological sort
  189.  
  190.     topological_sort();
  191.  
  192.     return 0;
  193. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top