Strongly Connected Component
1. Definition
- In a directed graph, the Strongly Connect Component is defined as the component in which every vertex is reachable from every other vertex.
2. Example
In the picture, (A, B, C), (D, E, F), (G,H,I,J) is three SCC.
3. How to Find All SCC
3.1 Kosaraju's Algorithm
Steps:
- Need a stack that stores by exploration finished time and a visited set
- For example, starting from B
- reverse the graph, and do DFS based on the stack, if it's not visited, do DFS and add them to a set, which is a SCC
- For example,
Proof
This will be guaranteed as an acycle graph
There is at least one vertex in ABC will be finished after DEF, and in GHIJ after DEF and K.
Let's say it's B and G, so after we reverse the Edge, it will become like this:
B will be at a higher position than any DFE, so B will be popped first to explore. Since it's reversed, ABC is concealed. So SCC(A, B, C) will be guaranteed.