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

Revision as of 17:47, 25 February 2022

Revision as of 15:52, 3 September 2022

Line 254:

: Well that would bring the pseudocode back to Tarjan's original. MattGiuca considered this above under Status of the algorithm and reasoned that v, just numbered, would have to be greater than any existing number. But while numbering v happens before looping over successors, it does seems that a recursive call to strongconnect on one successor of v could number a later successor of v. I'm inclined to agree that this looks like a problem but a test case might show it clearly. Do you have an example of a graph that shows this failure? —[[User:Fifteen Minutes Of Fame|Fifteen Minutes Of Fame]] ([[User talk:Fifteen Minutes Of Fame|talk]]) 15:56, 28 March 2015 (UTC)

:: v.lowlink can't be bigger than v.index, wo is w.index > v.index nothing will happen anyway. --[[User:Igor Yalovecky|Igor Yalovecky]] ([[User talk:Igor Yalovecky|talk]]) 15:52, 3 September 2022 (UTC)

== Relation to Kosaraju's algorithm ==