1
$\begingroup$

In Tarjan's algorithm for finding SCC/AP/Bridges, we update the value of the low[u] to be the min ( low[u], desc[v] ) given that v is a neighbor and has been discovered before, why it's not like this instead low[u] = min(low[u], low[v])?

$\endgroup$

closed as unclear what you're asking by D.W. Aug 20 '16 at 17:09

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Welcome to CS.SE! 1. This is unanswerable without looking at the specific version of Tarjan's algorithm you're looking at (e.g., the specific pseudocode you have in front of you). What's low[u]? desc[v]? I'm sure it's well-defined in the copy of the pseudocode you have, but others might have learned Tarjan's algorithm with pseudocode that uses different variable names. $\endgroup$ – D.W. Aug 20 '16 at 17:11
  • $\begingroup$ 2. What have you tried? Have you tried working through some small examples to see what happens if you use your proposed modification? Does it always give the right answer on all the examples you tried? Have you tried working through the proof of correctness for Tarjan's algorithm to see if you can modify it to prove your variant correct, or see which step it breaks down at? If you can address this feedback, edit your question accordingly and it can be considered for re-opening. $\endgroup$ – D.W. Aug 20 '16 at 17:12
  • $\begingroup$ I've seen the algorithm in this link here, and the question also appears in the same topic in this link geeksforgeeks.org/… $\endgroup$ – Kareem Aug 20 '16 at 17:49