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.
Tarjan Strongly Connected Components Question
graph theory;graph algorithms