Tarjan's algorithm

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.

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

Complexity

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

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
Rating (3): 4

See also

Comments





This article does not have any comments.