Tarjan Strongly Connected Components Question Below is Tarjan's SCC algorithm as described in wikipedia.

Input: Graph G = (V, E) 

1.  index = 0                                         // DFS node number counter 
2.  S = empty                                         // An empty stack of nodes 
3.  for all v in V do 
4.   if (v.index is undefined)                       // Start a DFS at each node 
5.     tarjan(v)                                     // we haven't visited yet 

6.  procedure tarjan(v) 
7.   v.index = index                                 // Set the depth index for v 
8.   v.lowlink = index                               
9.   index = index + 1 
10.  S.push(v)                                       // Push v on the stack 
11.  for all (v, v') in E do                         // Consider successors of v 
12.    if (v'.index is undefined)                    // Was successor v' visited? 
13.        tarjan(v')                                // Recurse 
14.        v.lowlink = min(v.lowlink, v'.lowlink) 
15.    else if (v' is in S)                          // Was successor v' in stack S? 
16.        v.lowlink = min(v.lowlink, v'.index)      // v' is in stack but it isn't in the dfs tree 
17.  if (v.lowlink == v.index)                       // Is v the root of an SCC? 
18.    print "SCC:" 
19.    repeat 
20.      v' = S.pop                                   
21.      print v' 
22.    until (v' == v)


In line 16, I could not determine why I could or could not replace line 16 with that of line 14. In other words, it seems to me that taking the min(v.lowlink, v'.lowlink) is the proper approach as opposed to min(v.lowlink, v'.index) in the above example. I have seen one other example on the web that mimics the pseudocode above.

I have considered the unusual use of stack S in the algorithm above in which S may contain items from previous "dead" stack frames. These leftover items aren't removed because they are not the roots of their own strongly connected component.
v.lowlink = min(v.lowlink, v'.index) in line 16 is indeed correct. For a full proof you can consult Tarjan's original paper which can also be found here.


  Robert Tarjan: Depth-first search and
  linear graph algorithms. In: SIAM
  Journal on Computing. Vol. 1 (1972),
  No. 2, P. 146-160.


Completely unrelated to the question, there is an amusing 1983 retrospective by Bob Tarjan here on the paper cited above.