A Strongly connected graph is a graph where each vertex could be visited from each other vertex of the graph, for example the following graph has 5 strongly connected components.
Algorithm to find SCC[]
One of the most famous algorithms that is used to find strongly connected components of a graph is known by the Kosaraju's algorithm. And It works as follows:
- DFS all nodes and save visited nodes in a stack S, push node only when finishing visit to all connected nodes.
- Inverse the original graph by reversing all arcs E(U, V) to be E(V, U) instead
- Pop each vertex V in S and DFS to get the strongly connected component that contains V.