Talk:Tarjan

Correctness?

The pseudo code from Wikipedia does not seem correct. I ran into problems when trying to translate it into Python. To corroborate, I tested the Perl code on the task page, with a simple graph where there are only two nodes with one directed edge between them: <lang perl>my %test1 = (

 0 => [1],

);

print "Strongly connected components:\n"; print join(', ', sort @$_) . "\n" for tarjan(%test1);</lang> which outputs

Strongly connected components:
1
0

Any thoughts? --Ledrug (talk) 08:37, 9 March 2020 (UTC)

   Perhaps the task description needs better detail. The code examples work if all points are those of a digraph so 0 => 1 means that 0 is 
   connected to 1 the same way as 1 is to 0. Note that the examples never show reciprocal connections -- if there is a 2 => 4,  we never 
   see 4 => 2 listed in the data --  it's a digraph.
   --Wherrera (talk) 08:19, 9 March 2020 (UTC)

That can't be right. "Strongly connected" means between two nodes A and B, there is a path from A to B *and* there is a path from B to A, which only makes sense if edges are directed. If all connections are bidirectional, there is no difference between "connected" and "strongly connected", and the algorithm only needs a depth-first traversal without much of the bookkeeping at all. --Ledrug (talk) 08:37, 9 March 2020 (UTC)