Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //TODO Find Strongly Connected Components
- //Kosaraju algorithm (DIRECTED GRAPHS)
- // 1.Do a topological sort and store the order in a stack
- // 2. Reverse the graph
- // 3. Traverse the reversed graph, popping the top of the stack and using that index as a parameter in the DFS function
- //INPUT GRAPH USED :
- //7
- //8
- //0 1 1
- //1 1 2
- //2 1 0
- //1 1 3
- //2 1 4
- //3 1 4
- //4 1 5
- //5 1 6
- //Global variables = pure laziness
- std::vector<std::list<Vertex>> reversed_graph;
- void topological_dfs(std::vector<bool>& visited,std::stack<int>& result,int from)
- {
- visited[from] = true;
- for(auto element:graph[from])
- {
- if(!visited[element.vertex_number])
- {
- visited[element.vertex_number] = true;
- topological_dfs(visited, result, element.vertex_number);
- }
- }
- result.push(from);
- }
- void components_topological(std::stack<int>& order_components)
- {
- std::vector<bool> visited(graph.size(), false);
- for(int i = 0; i<graph.size();i++)
- {
- if(!visited[i])
- {
- topological_dfs(visited, order_components, i);
- }
- }
- }
- void dfs_print(int from,std::vector<bool>&visited)
- {
- std::cout << from << " ";
- visited[from] = true;
- for(auto element:reversed_graph[from])
- {
- if(!visited[element.vertex_number])
- {
- visited[element.vertex_number] = true;
- dfs_print(element.vertex_number, visited);
- }
- }
- }
- void find_connected_components()
- {
- reversed_graph.resize(graph.size());
- std::stack<int> components_ordered;
- components_topological(components_ordered);
- reversed_graph = reverse_graph();
- std::vector<bool> visited_components(reversed_graph.size(), false);
- while(!components_ordered.empty())
- {
- if(!visited_components[components_ordered.top()])
- {
- dfs_print(components_ordered.top(), visited_components);
- std::cout << std::endl;
- }
- components_ordered.pop();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement