﻿ ﻿ Tarjan's algorithm

Tarjan's algorithm is a procedure for finding strongly connected components of a directed graph. A strongly connected component is a maximum set of vertices, in which exists at least one oriented path between every two vertices.

## Description

Tarjan's algorithm is based on depth first search (DFS). The vertices are indexed as they are traversed by DFS procedure. While returning from the recursion of DFS, every vertex gets assigned a vertex as a representative. is a vertex with the least index that can be reach from . Nodes with the same representative assigned are located in the same strongly connected component.

## Complexity

Tarjan's algorithm is only a modified depth first search, hence it has an asymptotic complexity .

## Code

```   index = 0

/*
* Runs Tarjan's algorithm
* @param g graph, in which the SCC search will be performed
* @return list of components
*/
List executeTarjan(Graph g)
Stack s = {}
List scc = {} //list of strongly connected components
for Node node in g
if (v.index is undefined)
tarjanAlgorithm(node, scc, s)

return scc

/*
* Tarjan's algorithm
* @param node processed node
* @param SCC list of strongly connected components
* @param s stack
*/
procedure tarjanAlgorithm(Node node, List scc, Stack s)
v.index = index
index++
for each Node n in Adj(node) do //for all descendants
if n.index == -1 //if the node was not discovered yet
tarjanAlgorithm(n, scc, s, index) //search
else if stack.contains(n) //if the component was not closed yet

if node.lowlink == node.index //if we are in the root of the component
Node n = null
List component //list of nodes contained in the component
do
n = stack.pop() //pop a node from the stack