Content deleted Content added
m Signing comment by Encyclopedant - "→Is there a minimal set of test cases somewhere?: new section" |
No edit summary |
||
Line 52:
014567
::No, I just tried out this case; both versions of code give the same output. [[User:MaigoAkisame|MaigoAkisame]] ([[User talk:MaigoAkisame|talk]]) 17:35, 4 January 2016 (UTC)
::This was changed once more, and I reverted the change. If someone wants to have w.lowlink in that line they should provide a REVIEWED reference proving that it works, and indicate that the original differed. Someone looking for Tarjan's algorithm on Wikipedia is likely looking for his algorithm - not some other algorithm that may or may not be correct. Assuming the modified algorithm was correct and faster (neither is clear) - how would you compare them: stating that Tarjan's algorithm is better than Tarjan's algorithm?
:::The [https://www.sciencedirect.com/science/article/abs/pii/S0020019015001532?via%3Dihub 2015 paper] linked from the Complexity section does basically <code>v.lowlink=min(v.lowlink,w.lowlink)</code> in Algorithm 3 PEA_FIND_SCC2(V,E). Perhaps we could have a section discussing variations to the algorithm? --[[User:Thomasda|Thomasda]] ([[User talk:Thomasda|talk]]) 10:20, 27 May 2020 (UTC)
[[Special:Contributions/195.190.84.155|195.190.84.155]] ([[User talk:195.190.84.155|talk]]) 12:04, 11 April 2017 (UTC)
:Use v.lowlink = min(v.lowlink, w.index) give lowlink a more meaningful definition: it is the node with the smallest index v can reach with only one back edge. If min(v.lowlink, w.lowlink) is used, the lowlink will loss its meaning (for clarity, let's call this definition lowlink'). If w is a parent of v in the DFS tree, its lowlink' is not finalized, and could still change. This means you can not just define v.lowlink' as the smallest index v can reach, because that is not necessarily true.
:For example:
| |||