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

Revision as of 17:56, 4 August 2009

Revision as of 10:50, 10 December 2009

Line 36:

I've fixed the algorithm, it should make much more sense now. I hope there aren't any more bugs. [[Special:Contributions/70.68.114.213|70.68.114.213]] ([[User talk:70.68.114.213|talk]]) 02:40, 31 January 2009 (UTC)

== Node with no successor ==

Isn't there an issue for node that have no successor ? In that case, the main procedure can be seen like :

<pre>

v.index = index // Set the depth index for v

v.lowlink = index

index = index + 1

S.push(v) // Push v on the stack

if (v.lowlink == v.index) // Is v the root of an SCC?

print "SCC:"

repeat

v' = S.pop

print v'

until (v' == v)

</pre>

(The "forall (v, v') loop is not executed). It results in such a node to be always reported as strongly connected root, while in my understanding it can't be.