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

Revision as of 06:37, 8 February 2011

Revision as of 06:58, 8 February 2011

Line 128:

Remark that my modifications answer to the Node-without-successor problem above mentioned :-)

* I don't see why you should set v.lowindex to v.index + 1. (By lowindex do you mean lowlink?) The lowlink is the index of the lowest-known root in the current node's SCC, which is initially assumed to be ''this'' node, not the ''next'' node. It ''is'' the case that "All the vertices such that v.index = v.lowlink are root of a Scc", but it is ''not'' the case that "All the vertices such that v.index >= v.lowlink belong to the Scc" -- rather, I would say that all the vertices with v.index > v.lowlink belong to ''some'' SCC, and are not the root of it. There *are* no vertices with v.index < v.lowlink -- the min checks ensure that no vertex has a lowlink greater than its own index. There is also no "tree part of the graph" -- every node belongs to an SCC (though nodes which are not involved in cycles form a single-node SCC). Therefore these modifications are not useful. '''Not an issue''' &mdash;[[User:MattGiuca|MattGiuca]] ([[User talk:MattGiuca|talk]]) 06:58, 8 February 2011 (UTC)

== Counterexample ==