# 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

Tweet | ||

Rating (4):
4