Talk:Tarjan's strongly connected components algorithm: Difference between revisions

Revision as of 07:05, 23 April 2008

Revision as of 19:11, 6 January 2009

Line 9:

--[[Special:Contributions/211.25.51.200|211.25.51.200]] ([[User talk:211.25.51.200|talk]]) 07:05, 23 April 2008 (UTC)

== 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'')

--[[Special:Contributions/128.9.216.61|128.9.216.61]] ([[User talk:128.9.216.61|talk]]) 19:11, 6 January 2009 (UTC)