An example implementation of my algorithm for finding Strongly Connected Components.
Java
Switch branches/tags
Nothing to show
Clone or download

README.md

StronglyConnectedComponents

Two example implementations of my algorithm for finding strongly connected components in a directed graph. This algorithm improves the space requirements of Tarjan's by compressing two arrays into one. See the following paper for details of how the algorithm works:

  • "An Improved Algorithm for Finding the Strongly Connected Components of a Directed Graph", David J. Pearce, 2015.

Both a recursive and imperative version of this algorithm are given for completeness. These algorithms are not intended to be specifically efficient, just to provide sample implementations. In particular, I've tried to keep them as close to the presentation in the paper as possible.

Documentation

  • A preprint version of the paper can be obtained here.

  • A nice blog article of the algorithm can be found here.