Strongly Connected Components - GeeksforGeeks
A directed graph is strongly connected if there is a path between all pairs of vertices. A strongly connected component (SCC) of a directed graph is a maximal strongly connected subgraph.
We can find all strongly connected components in O(V+E) time using Kosaraju’s algorithm. Following is detailed Kosaraju’s algorithm.
1) Create an empty stack ‘S’ and do DFS traversal of a graph. In DFS traversal, after calling recursive DFS for adjacent vertices of a vertex, push the vertex to stack.
2) Reverse directions of all arcs to obtain the transpose graph.
3) One by one pop a vertex from S while S is not empty. Let the popped vertex be ‘v’. Take v as source and do DFS (call DFSUtil(v)). The DFS starting from v prints strongly connected component of v.
The above algorithm is DFS based. It does DFS two times.
if we do a DFS of graph and store vertices according to their finish times, we make sure that the finish time of a vertex that connects to other SCCs (other that its own SCC), will always be greater than finish time of vertices in the other SCC.
So to use this property, we do DFS traversal of complete graph and push every finished vertex to a stack.
Java Code: https://sites.google.com/site/indy256/algo/strongly_connected_components
https://www.geeksforgeeks.org/tarjan-algorithm-find-strongly-connected-components/
A directed graph is strongly connected if there is a path between all pairs of vertices. A strongly connected component (SCC) of a directed graph is a maximal strongly connected subgraph.
We can find all strongly connected components in O(V+E) time using Kosaraju’s algorithm. Following is detailed Kosaraju’s algorithm.
1) Create an empty stack ‘S’ and do DFS traversal of a graph. In DFS traversal, after calling recursive DFS for adjacent vertices of a vertex, push the vertex to stack.
2) Reverse directions of all arcs to obtain the transpose graph.
3) One by one pop a vertex from S while S is not empty. Let the popped vertex be ‘v’. Take v as source and do DFS (call DFSUtil(v)). The DFS starting from v prints strongly connected component of v.
The above algorithm is DFS based. It does DFS two times.
if we do a DFS of graph and store vertices according to their finish times, we make sure that the finish time of a vertex that connects to other SCCs (other that its own SCC), will always be greater than finish time of vertices in the other SCC.
So to use this property, we do DFS traversal of complete graph and push every finished vertex to a stack.
void Graph::printSCCs(){ stack<int> Stack; // Mark all the vertices as not visited (For first DFS) bool *visited = new bool[V]; for(int i = 0; i < V; i++) visited[i] = false; // Fill vertices in stack according to their finishing times for(int i = 0; i < V; i++) if(visited[i] == false) fillOrder(i, visited, Stack); // Create a reversed graph Graph gr = getTranspose(); // Mark all the vertices as not visited (For second DFS) for(int i = 0; i < V; i++) visited[i] = false; // Now process all vertices in order defined by Stack while (Stack.empty() == false) { // Pop a vertex from stack int v = Stack.top(); Stack.pop(); // Print Strongly connected component of the popped vertex if (visited[v] == false) { gr.DFSUtil(v, visited); cout << endl; } }}https://www.geeksforgeeks.org/tarjan-algorithm-find-strongly-connected-components/
