

 This page uses content from Wikipedia. The original article was at Graph. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance)



Tarjan's algorithm is an algorithm in graph theory for finding the strongly connected components of a graph.

It runs in linear time, matching the time bound for alternative methods including Kosaraju's algorithm and the path-based strong component algorithm.

Tarjan's Algorithm is named for its discoverer, Robert Tarjan.



References

 The article on Wikipedia.


class Tarjan{
   // input: graph G = (V, Es)
   // output: set of strongly connected components (sets of vertices)
   // Ick: class holds global state for strongConnect(), otherwise inert
   const INDEX=0, LOW_LINK=1, ON_STACK=2;
   fcn init(graph){
      var index=0, stack=List(), components=List(),
          G=List.createLong(graph.len(),0);
 
      // convert graph to ( (index,lowlink,onStack),(id,links)), ...)
      // sorted by id
      foreach v in (graph){ G[v[0]]=T( L(Void,Void,False),v) }
 
      foreach v in (G){ if(v[0][INDEX]==Void) strongConnect(v) }
 
      println("List of strongly connected components:");
      foreach c in (components){ println(c.reverse().concat(",")) }
 
      returnClass(components);  // over-ride return of class instance
   }
   fcn strongConnect(v){  // v is ( (index,lowlink,onStack), (id,links) )
      // Set the depth index for v to the smallest unused index
      v0:=v[0]; v0[INDEX]=v0[LOW_LINK]=index;
      index+=1;
      v0[ON_STACK]=True;
      stack.push(v);
 
       // Consider successors of v
      foreach idx in (v[1][1,*]){  // links of v to other vs
         w,w0 := G[idx],w[0];   // well, that is pretty vile
     if(w[0][INDEX]==Void){
        strongConnect(w); // Successor w not yet visited; recurse on it
        v0[LOW_LINK]=v0[LOW_LINK].min(w0[LOW_LINK]);
     }
     else if(w0[ON_STACK])
        // Successor w is in stack S and hence in the current SCC
        v0[LOW_LINK]=v0[LOW_LINK].min(w0[INDEX]);
      }
      // If v is a root node, pop the stack and generate an SCC
      if(v0[LOW_LINK]==v0[INDEX]){
         strong:=List();  // start a new strongly connected component
     do{
        w,w0 := stack.pop(), w[0];
        w0[ON_STACK]=False;
        strong.append(w[1][0]); // add w to strongly connected component
     }while(w.id!=v.id);
     components.append(strong); // output strongly connected component
      }
   }
}