Strongly Connected Components
Two nodes are considered to be mutually connected if you can go from node a to node b and from node b to node a.
A graph is said to be strongly connected if every node is mutually connected. That is, every node can reach every other node and vise versa.
English Algorithm
Start from any node S.
Preform DFS starting from node S. Add elements by their earliest finish time into a stack. An node is considered to be finished when it can no longer explore any children.
Step 1, until all nodes of the graph are explored.
Reverse all the edges in graph
Start from any node S in the reversed graph.
Perform DFS starting from elements on top of the stack, popping off you go. Explore node S, and this will return the elements within the strongly connected component.
** Ensure that during this process, nodes are visited only once.
Example
The following graph has 4 strongly connected components.
Why this Works
Consider the simplified version of this graph
Where every strongly connected component is represented as a single node in this graph. The remaining edges that connect the these components together produce the remainder of the graph.
We know a few things about this graph. First, it is guaranteed to be a DAG. If it was otherwise cyclic, then the cycle would mean there would be another simplification the above graph that would combine two strongly connected components.
Secondly, the order of earliest finish would mean that there is at least one node in ABC that remains unexplored because the DFS algorithm would continue to explore DEF.
So if we transpose this graph, then we are ensuring that the nodes finished first get explored last. So now even if DEF has the chance to explore both ABC and HIGJ the algorithm ensure that both of these components were already explored and so DEF remains on its own.
Last updated
