Talk:Tarjan's strongly connected components algorithm
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
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)
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)
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)