About tarjan algorithm, why can't we take low[v] instead of disc[v] when considering the backward edge?
Asked Answered
A

0

6

I read an article about Tarjan's algorithm, blog. In this article, the author asks a question:

In case two, can we take low[v] instead of disc[v] ?? . Answer is NO. If you can think why answer is NO, you probably understood the Low and Disc concept.

I don't know why. When I am reading the similar article in wiki, I found that the code can be like that:

     else if (w.onStack) then
    // Successor w is in stack S and hence in the current SCC
    v.lowlink  := min(v.lowlink, w.lowlink)

I wanna know why the author say the answer is NO. Thanks for answering my question. Have a good day.

Abbess answered 10/3, 2017 at 7:34 Comment(2)
I can't tell for sure (Tarjan used min(low, disc) in his original paper), but to me either way is fine. It certainly does matter when you search for bridges and/or articulation points - in such a case using low would imply that you can jump in the backward direction multiple times (not using only a single edge) and thus skip articulation points. However, In the case of finding sccs, all you need is to know if you can go to some earlier vertex within the same scc, and so, you make low[v] <> disc[v], and that's what matters.Winnick
Using min(low, disc) is closer to the actual definition of what low function is which in turn is present also in the aforementioned algorithms, thus I guess that's the reason why disc is here.Winnick

© 2022 - 2024 — McMap. All rights reserved.