Talk:Tarjan's strongly connected components algorithm

Mathematics C‑class Low‑priority

	Mathematics portal This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics
C	This article has been rated as C-class on Wikipedia's content assessment scale.
Low	This article has been rated as Low-priority on the project's priority scale.

Pseudocode is not good

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

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]

Both versions are correct, since v'.lowlink is the same as v'.index for the root of a strongly connected component. Therefore, I suggest to revert this change to the previous version, where the update is uniform in both branches. —Preceding unsigned comment added by 192.35.241.121 (talk) 17:55, 4 August 2009 (UTC)[reply]

Algorithm fixed

I've fixed the algorithm, it should make much more sense now. I hope there aren't any more bugs. 70.68.114.213 (talk) 02:40, 31 January 2009 (UTC)[reply]

Node with no successor

Isn't there an issue for node that have no successor ? In that case, the main procedure can be seen like :

  v.index = index                 // Set the depth index for v
  v.lowlink = index
  index = index + 1
  S.push(v)                       // Push v on the stack
  if (v.lowlink == v.index)       // Is v the root of an SCC?
    print "SCC:"
    repeat
      v' = S.pop
      print v'
    until (v' == v)

(The "forall (v, v') loop is not executed). It results in such a node to be always reported as strongly connected root, while in my understanding it can't be. —Preceding unsigned comment added by 90.80.39.42 (talk) 10:50, 10 December 2009 (UTC)[reply]