Strongly connected components of a Graph – Kosaraju in Java

The Kosaraju algorithm can be used that if the underlying store is an AdjacencyList can be blazing fast with O (V+E) time.

Implemented as per wiki:

  1. Let G be a directed graph and S be an empty stack.
  2. While S does not contain all vertices:
    • Choose an arbitrary vertex v not in S. Perform a depth-first search starting at v. Each time that depth-first search finishes expanding a vertex u, push u onto S.
  3. Reverse the directions of all arcs to obtain the transpose graph.
  4. While S is nonempty:
    • Pop the top vertex v from S. Perform a depth-first search starting at v in the transpose graph. The set of visited vertices will give the strongly connected component containing v; record this and remove all these vertices from the graph G and the stack S. Equivalently, breadth-first search (BFS) can be used instead of depth-first search.

Source Code: