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

Ad blocker interference detected!

Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.