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:
Kosaraju

  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:

Leave a Reply

Your email address will not be published. Required fields are marked *

     

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">