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
- Create a Stack.
- Traverse Graph in DFS order
- Put visited vertex in stack only when all adjacent vertex of that vertex visited
- Reverse the edges of graph
- And traverse graph using vertices that in stack
Intuition behind Kosaraju algorithm
Latest Source Code:
Github: GraphStronglyConnectedComponent.java
Output:
[0, 1, 2] [3] [4]