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 Edit

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.

See Also Edit