Talk:Kosaraju's algorithm: Difference between revisions

Revision as of 15:59, 26 November 2015

Latest revision as of 18:59, 4 February 2024

(4 intermediate revisions by 3 users not shown)

Line 1:

{{mathsWikiProject ratingbanner shell|class=Start|priority=Low|field=discrete}}

{{WikiProject ComputingMathematics|classpriority=Stub|importance=|auto=yesLow}}

{{WikiProject Computing|importance=Low|auto=no}}

}}

{{Broken anchors|links=

* <nowiki>[[Tree_traversal#Post-order|post-order]]</nowiki> The anchor (#Post-order) is no longer available because it was [[Special:Diff/1083604422|deleted by a user]] before. <!-- {"title":"Post-order","appear":{"revid":532658304,"parentid":532657304,"timestamp":"2013-01-12T06:05:42Z","removed_section_titles":["Preorder","Inorder","Postorder","Threading and Morris inorder traversal"],"added_section_titles":["Pre-order","In-order","Post-order","Threading and Morris in-order traversal"]},"disappear":{"revid":1083604422,"parentid":1083603432,"timestamp":"2022-04-19T18:07:39Z","removed_section_titles":["Depth-first search","Post-order","In-order"],"added_section_titles":["Preorder traversal","Pre-order traversal","Postorder traversal","Post-order traversal","Reverse preorder traversal","Reverse pre-order traversal","Reverse postorder traversal","Reverse post-order traversal","Reverse inorder traversal","Reverse in-order traversal","Depth-first search implementation","Pre-order traversal code","Post-order implementation","Post-order traversal code","In-order implementation","Inorder traversal code","In-order traversal code"]}} -->

}}

==Confusion==

Line 12 ⟶ 17:

::[5] Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. Data Structures and Algorithms. Addison-Wesley, 1983.

:I would suggest that someone goes to a library and checks what is actually stated in reference [5]. (Sigh. I suppose that errors which cannot be verified with the aid of an internet search engine will actually never be fixed on wikipedia.) [[Special:Contributions/134.176.28.77|134.176.28.77]] ([[User talk:134.176.28.77|talk]]) 13:08, 10 August 2009 (UTC)

::I checked reference 5, it says that Kosaraju discovered it in 1978 (unpublished) and that Sharir published it in the mentioned article from 1981. [[User:Nczempin|Nczempin]] ([[User talk:Nczempin|talk]]) 23:46, 28 January 2023 (UTC)

== Text excised from [[2-satisfiability]] ==

Line 21 ⟶ 27:

That actually gives a ''better'' description of the algorithm than the text currently in the article.[[Special:Contributions/130.243.83.63|130.243.83.63]] ([[User talk:130.243.83.63|talk]]) 15:58, 26 November 2015 (UTC)

== Incorrect claim in algo description ==

The article states: "so if there is a forward path from ''u'' to ''v'' then ''u'' will appear before ''v'' on the final list ''L'' (unless ''u'' and ''v'' both belong to the same strong component, in which case their relative order in ''L'' is arbitrary)."

This is not true. There is a weaker claim which is both true and sufficient to justify the algorithm correctness: If there is a path from ''u'' to ''v'' and ''u'' and ''v'' belong to different strongly connected components then there is some vertex from ''u''{{'}}s strongly connected component that appears on the final list L before all vertices in ''v''{{'}}s strongly connected component. Importantly, not all vertices from ''u''{{'}}s SCC need to appear on L before all vertices from ''v''{{'}}s SCC, which is implied by the original claim.

[[User:Pilloff|Pilloff]] ([[User talk:Pilloff|talk]]) 19:13, 21 April 2022 (UTC)