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
v.lowlink = index
index++
s.push(node) //add to the stack
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
node.lowlink = min(node.lowlink, n.lowlink) //modify parent's lowlink
else if stack.contains(n) //if the component was not closed yet
node.lowlink = min(node.lowlink, n.index) //modify parents lowlink
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
component.add(n) //and add it to the component
while(n != v) //while we are not in the root
scc.add(component) //add the compoennt to the SCC list