# A Space Efficient Algorithm for Detecting Strongly Connected Components

**Author(s).** David J. Pearce.

**Venue.**
In *Information Processing Letters,*
116
(1),
pages 47--52,
2016.
©Elsevier

**Abstract.** Tarjan’s algorihm for finding the strongly connected components of a directed graph is widely used and acclaimed. His original algorithm required at most `v(2 + 5w)`

bits of storage, where w is the machine’s word size, whilst Nuutila and Soisalon-Soininen reduced this to `v(1 + 4w)`

. Many real world applications routinely operate on very large graphs where the storage requirements of such algorithms is a concern. We present a novel improvement on Tarjan’s algorithm which reduces the space requirements to `v(1 + 3w)`

bits in the worst case. Furthermore, our algorithm has been independently integrated into the widely-used SciPy library for scientific computing.

**Notes.** This algorithm was incorporated into SciPy, a widely used Python Library for scientific computing (see here). Some discussion of the SciPy implementation can be found here as well. A straightforward Java implementation of the algorithm is available here and another C++ implementation is available here.