The Kosaraju-Sharir Algorithm

The Kosaraju-Sharir algorithm finds the strongly connected components of a digraph by requiring two passes of depth-first search. While this algorithm performs more work than Tarjan’s algorithm, it’s elegant in its simple presentation and is easier to understand. Interestingly, despite the extra work, its running time remains asymptotically the same as that of depth-first search, i.e., $O(n+m)$, where $n$ and $m$ are the numbers of vertices and edges, respectively.

The algorithm was published in 1981 by Micha Sharir but is also attributed independently to S. Rao Kosaraju (unpublished, 1978).

Before we describe the algorithm, let’s first talk about the transpose of a digraph, as it’s directly relevant to the algorithm’s implementation.

Transpose of a digraph

Given a digraph $G$, if the directions on all the edges are reversed, the resulting digraph $G'$ is called the transpose of $G$.

That’s a neat little name for referring to the resultant graph, seeing that the adjacency matrix of $G'$ really is the transpose of the adjacency matrix of $G$.

Here’s an example of a digraph and its transpose:

Clearly, the transpose of the transpose of $G$ is the digraph $G$ itself.

Computing the transpose graph

It’s not hard to see how, given the adjacency list of a digraph $G$, we can create an adjacency list of the transpose digraph $G'$.

• $O(n)$ time is needed to create an empty list against each vertex.
• As each edge $(u,v)$ on the adjacency list of $u$ in $G$ is read, it is inserted against $v$ in time $O(1)$ at the head of its adjacency list. So, over all the edges, $O(n+m)$ time is taken.

Think, think, think

Let’s explore some facts that follow directly from the definition of transpose digraphs.

Fact: Suppose ...