Talk:Tarjan's strongly connected components algorithm

Pseudocode is not good

Latest comment: 17 years ago1 comment1 person in discussion

In this reference web.cecs.pdx.edu we see that TarjanDfs is called not only for first node v0, but all nodes that are not visited. This should be fixed, I am not expert, but here is suggestion.

index = 0                       // DFS node number counter 
S = empty                       // An empty stack of nodes
for each vertex v
 if v.index is undefined
  tarjan(v)                      // Start a DFS at the non-visited node

--211.25.51.200 (talk) 07:05, 23 April 2008 (UTC)Reply

Bug in second subcase

Latest comment: 16 years ago1 comment1 person in discussion

Seems to me that the second update case is wrong:

Instead of

   if (v'.index is undefined)  // Was successor v' visited? 
     tarjan(v')                // Recurse
     v.lowlink = min(v.lowlink, v'.lowlink)
   elseif (v' in S)            // Is v' on the stack?
     v.lowlink = min(v.lowlink, v'.lowlink)

shouldn't it be

   if (v'.index is undefined)  // Was successor v' visited? 
     tarjan(v')                // Recurse
     v.lowlink = min(v.lowlink, v'.lowlink)
   elseif (v' in S)            // Is v' on the stack?
     v.lowlink = min(v.lowlink, v'.index)

--128.9.216.61 (talk) 19:11, 6 January 2009 (UTC)Reply