Tarjan's Algorithm

Tarjan’s algorithm is a modification of the Bridge Finding Algorithm except for directed graphs. We maintain a stack, with the following invariant:

Let $S$ be a stack with vertices $v_1, \dots, v_k$. For a vertex $v_{k + 1}$ to be added onto the stack, there must exist a path from vertex $v_{k+1}$ to some previous vertex existing in the stack, $v_1,\dots,v_k$.

We define a recursive function $f$ that takes in a vertex $v$ that returns all strongly connected components that can be reached from $v$. Else, $f$ adds the vertices that has a back-edge into a vertex located in the stack into the stack

We will explain the algorithm by proving it.

Proof

Base case: $v$ has no children Suppose $v$ has no children, then $v$ itself is the connected component.

Induction step: Suppose $v$ has $k + 1$ children. We assume $f$ can solve for $k$ children of $v$.

Suppose we run $f$ for all $k$ children of $v$. We will extract all connected components that can be reached from each of the $k$ children of $v$. We also add the vertices reachable from these $k$ children that have a path to a vertex existing in the stack.

The stack $S$ after running $f$ on $k$ children will contain all vertices in the search tree that points back to $v$ or a vertex above $v$ within the stack.

For the $k+1$ child let this child be $w$.

Suppose $w$ exists in the stack, then we update $v$ with a lowlink of the timestep of $w$. Now, $S$ contains all vertices that has a path back to the root $v$. We can now pop all vertices in $S$ to get the connected component of $v$.

Suppose $w$ does not exist in the stack, then we add $w$ to the stack, then iterate through all its adjacent vertices to $w$ and run $f$.

Suppose a path does not exist from $w$ to a vertex before $w$ in the stack, then $w$ and all the vertices after $w$ present in the stack will form a strongly connected component. We pop all vertices in $S$ up to $w$ and add them to the component.

Suppose a path exists from $w$ to a vertex before $w$ in the stack, then we can update the lowlink of $w$ to that vertex. Then the lowlink of $v$ will be the lowlink of $w$.

Suppose an adjacent vertex isn’t in the stack, we run $f$ on that vertex to obtain the connected components reachable from the children of that vertex, and to obtain vertices that point back to a We run $f$ on all children of $w$ that does not exist on the stack to obtain the connected components reachable from children of $w$. Vertices that have a back edge into a vertex within the stack are also added into the stack.

We now iterate and pop through the stack till we find a vertex with a low value that equals to its timestep. Let this vertex be $u$.. All vertices popped should have a path that points back to $u$.