Strongly connected components- Kosaraju’s algorithm

Before starting with Kosaraju’s algorithm, you might want to revisit Depth first and beadth first algorithms.

http://kamalmeet.com/algorithms/depth-first-search/
http://kamalmeet.com/algorithms/breadth-first-search/

Refer the following graph

scc

vertex a,b in a graph are stringly connected if a is reachable from b and b is reachable from a.

In above graph, ABCD subgraph is strongly connected.

Kosaraju’s algorithm helps in finding all such strongly connected components in a graph.

1. Run Depth first search (DFS) on the graph and add verticies on a stack S.
2. Reverse (transpose) the graph by reversing directions of all the edges.
3. Pull a vertext v fron Stack S (step 1), run DFS on on vertex on reversed graph created in step 2. All the nodes found in DFS from vertex v are stringly connected. Remove all nodes found in DFS from reversed graph and stack S.

Further reads-

https://en.wikipedia.org/wiki/Strongly_connected_component

https://en.wikipedia.org/wiki/Kosaraju’s_algorithm
http://www.geeksforgeeks.org/strongly-connected-components/

Leave a Reply