Tarjan's algorithm
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.


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 V gets assigned a vertex L as a representative. L is a vertex with the least index that can be reach from V. Nodes with the same representative assigned are located in the same strongly connected component.


Tarjan's algorithm is only a modified depth first search, hence it has an asymptotic complexity O(|V| + |E|).


   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
       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
               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

INFO WEB s.r.o.

Company INFO WEB s.r.o. offers development of systems, GIS, presentations and interactive maps, using the microcontrollers from the IoT (Tnternet of Things) technology. Beside this on PROGRAMMING-ALGORITHMS.NET we publish some of the algorithms, which helps to solve some of the spatial analysis and spatial problems, conversion of coordinate systems and helps to solve standard computing operations.


Place for your banner

Here is the position ready for our customer's banners.