Advertisement
arsovski

Strong Connected Components(Directed Graph)

Jan 21st, 2020
91
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.83 KB | None | 0 0
  1. //TODO Find Strongly Connected Components
  2. //Kosaraju algorithm  (DIRECTED GRAPHS)
  3. //  1.Do a topological sort  and store the order in a stack
  4. //  2. Reverse the graph
  5. //  3. Traverse the reversed graph, popping the top of the stack and using that index as a parameter in the DFS function
  6.  
  7. //INPUT GRAPH USED :
  8.  
  9. //7
  10. //8
  11.  
  12. //0 1 1
  13. //1 1 2
  14. //2 1 0
  15. //1 1 3
  16. //2 1 4
  17. //3 1 4
  18. //4 1 5
  19. //5 1 6
  20.  
  21.  
  22. //Global variables = pure laziness
  23.  
  24. std::vector<std::list<Vertex>> reversed_graph;
  25.  
  26. void topological_dfs(std::vector<bool>& visited,std::stack<int>& result,int from)
  27. {
  28.     visited[from] = true;
  29.     for(auto element:graph[from])
  30.     {
  31.         if(!visited[element.vertex_number])
  32.         {
  33.             visited[element.vertex_number] = true;
  34.             topological_dfs(visited, result, element.vertex_number);
  35.         }
  36.     }
  37.  
  38.     result.push(from);
  39. }
  40.  
  41. void components_topological(std::stack<int>& order_components)
  42. {
  43.     std::vector<bool> visited(graph.size(), false);
  44.     for(int i = 0; i<graph.size();i++)
  45.     {
  46.         if(!visited[i])
  47.         {
  48.             topological_dfs(visited, order_components, i);
  49.         }
  50.     }
  51. }
  52.  
  53. void dfs_print(int from,std::vector<bool>&visited)
  54. {
  55.     std::cout << from << " ";
  56.     visited[from] = true;
  57.     for(auto element:reversed_graph[from])
  58.     {
  59.         if(!visited[element.vertex_number])
  60.         {
  61.             visited[element.vertex_number] = true;
  62.             dfs_print(element.vertex_number, visited);
  63.         }
  64.     }
  65. }
  66.  
  67. void find_connected_components()
  68. {
  69.     reversed_graph.resize(graph.size());
  70.     std::stack<int> components_ordered;
  71.     components_topological(components_ordered);
  72.  
  73.     reversed_graph = reverse_graph();
  74.  
  75.  
  76.     std::vector<bool> visited_components(reversed_graph.size(), false);
  77.     while(!components_ordered.empty())
  78.     {
  79.         if(!visited_components[components_ordered.top()])
  80.         {
  81.             dfs_print(components_ordered.top(), visited_components);
  82.             std::cout << std::endl;
  83.         }
  84.         components_ordered.pop();
  85.     }
  86. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement