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

Revision as of 06:35, 8 February 2011

Revision as of 06:37, 8 February 2011

Line 110:

Ok, I worked on it!!

In my opinion the pseudocode is wrong. The right order when calling Tarjan is:

v.index = index;

index = index + 1;

v.lowindex = index;

v.index = index;

then the law to update v.lowindex is

index = index + 1;

v.lowindex <- min(v'.lowindex, v'.index, v.lowindex);

v.lowindex = index;

then the law to update v.lowindex is

v.lowindex <- min(v'.lowindex, v'.index, v.lowindex);

What you have as result is that

1)# All the vertices such that v.index >= v.lowindex belong to the Scc,

2)# All the vertices such that v.index = v.lowindex are root of a Scc

3)# All the vertices such that v.index < v.lowindex belong to the tree part of the graph.

I hope my modifications respect the original Tarjan algorithm,