Strongly Connected Components by Kosaraju’s algorithm

• A graph is said to be strongly connected if there is a path from each vertex to every other vertex i.e if u and v are two vertices then there is a path from u to v and also from v to u.
• A directed graph is strongly connected if there is a path between all pairs of vertices.
• A strongly connected component (SCC) of a directed graph is a maximal strongly connected subgraph.

Algorithm

1. Create a Stack.
2. Traverse Graph in DFS order
   1. Put visited vertex in stack only when all adjacent vertex of that vertex visited
3. Reverse the edges of graph
4. And traverse graph using vertices that in stack

Video

Intuition behind Kosaraju algorithm

S. Rao Kosaraju

Latest Source Code:
Github: GraphStronglyConnectedComponent.java

Output:

[0, 1, 2]
[3]
[4]