<p><code>v.lowlink = min(v.lowlink, v'.index)</code> in line 16 is indeed correct. For a full proof you can consult Tarjan's original paper which can also be found <a href="http://dutta.csc.ncsu.edu/csc791_spring07/wrap/dfs.pdf" rel="nofollow">here</a>.</p>

<blockquote>
  <p>Robert Tarjan: Depth-first search and
  linear graph algorithms. In: SIAM
  Journal on Computing. Vol. 1 (1972),
  No. 2, P. 146-160.</p>
</blockquote>

<p>Completely unrelated to the question, there is an amusing 1983 retrospective by Bob Tarjan <a href="http://www.garfield.library.upenn.edu/classics1983/A1983QY47200001.pdf" rel="nofollow">here</a> on the paper cited above.</p>

CC BY-SA 4.0
2020-05-27T10:23:20.283Z
It actually works fine the other way too. That's because `lowlink` will never point outside of the current SCC. It's reminiscent of Algorithm 3 in https://www.sciencedirect.com/science/article/abs/pii/S0020019015001532?via%3Dihub
Thomas Ahle
CC BY-SA 2.5
2010-11-16T05:07:47.383Z
2010-11-16T05:15:14.553Z
2010-11-16T05:15:14.553Z
Michael
<p>Below is Tarjan's SCC algorithm as described in <a href="http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm#The_root_property" rel="nofollow" title="wikipedia">wikipedia</a>.</p>

<p>Input: Graph G = (V, E) </p>

<pre><code>1.  index = 0                                         // DFS node number counter 
2.  S = empty                                         // An empty stack of nodes 
3.  for all v in V do 
4.   if (v.index is undefined)                       // Start a DFS at each node 
5.     tarjan(v)                                     // we haven't visited yet 

6.  procedure tarjan(v) 
7.   v.index = index                                 // Set the depth index for v 
8.   v.lowlink = index                               
9.   index = index + 1 
10.  S.push(v)                                       // Push v on the stack 
11.  for all (v, v') in E do                         // Consider successors of v 
12.    if (v'.index is undefined)                    // Was successor v' visited? 
13.        tarjan(v')                                // Recurse 
14.        v.lowlink = min(v.lowlink, v'.lowlink) 
15.    else if (v' is in S)                          // Was successor v' in stack S? 
16.        v.lowlink = min(v.lowlink, v'.index)      // v' is in stack but it isn't in the dfs tree 
17.  if (v.lowlink == v.index)                       // Is v the root of an SCC? 
18.    print "SCC:" 
19.    repeat 
20.      v' = S.pop                                   
21.      print v' 
22.    until (v' == v)
</code></pre>

<p>In line 16, I could not determine why I could or could not replace line 16 with that of line 14. In other words, it seems to me that taking the min(v.lowlink, v'.lowlink) is the proper approach as opposed to min(v.lowlink, v'.index) in the above example. I have seen one other example on the web that mimics the pseudocode above.</p>

<p>I have considered the unusual use of stack S in the algorithm above in which S may contain items from previous "dead" stack frames. These leftover items aren't removed because they are not the roots of their own strongly connected component.</p>

CC BY-SA 2.5
2010-11-16T04:24:52.810Z
Implementation and programming questions like this are more appropriate for StackOverflow, this site is for *theoretical computer science* questions. I also don't see a question in this post. Voting to close as off-topic.
Kaveh
CC BY-SA 2.5
2010-11-16T04:35:27.130Z
I have to agree... I can't find anything concrete in the question that asks about the concepts of the algorithm itself. Instead, just questions about/problems with the implementation... You should consider [StackOverflow](http://stackoverflow.com/)
Daniel Apon
CC BY-SA 2.5
2010-11-16T05:24:31.283Z
If I understand him correctly, he's unsure if line 16 is correct. That is, he wants to know if one shouldn't put v'.lowlink instead of v'.index for the algorithm to be correct.
Michael
CC BY-SA 2.5
2010-11-16T05:48:55.437Z
@Michael: I don't think that is a *theoretical* computer science question (let alone a research-level one, it can be answered by looking at the proof of correctness of the algorithm in textbooks on graph algorithms).
Kaveh
CC BY-SA 2.5
2010-11-16T05:48:58.987Z
@Kaveh: Just wanted to help :) I think proving correctness of algorithms can count as theoretical computer science. But I agree that it is not research-level and could be easily checked (for some people).

Then again, I think time is better spent if one gives a short answer in certain cases rather than to argue if something is "worthy" of an answer :)
Michael
CC BY-SA 2.5
2010-11-16T05:54:10.907Z
@Michael: I understand that you want to help, and proving correctness of *algorithms* (not implementations) *can* count as theoretical computer science, but answering this kind of questions can have a longer term effect on the level of question posted on the site. (ps: I am not saying this is not worthy of answering, just saying this is not the right place for this question and StackOverflow is more suitable for it, please see the discussions on the meta about homework questions to understand my point.)
Kaveh
CC BY-SA 2.5
2010-11-16T06:09:27.440Z
@Michael: ps: IMHO it is not a nice practice to post an answer when a question is being closed. In the case you disagree with closing the question, it is nicer to post your opinion as a comment and wait for a decision before posting an answer.
Kaveh
CC BY-SA 2.5
2010-11-16T06:22:20.783Z
@Kaveh: Didn't see the comments when I posted the answer. Just saw the upvotes.
Michael
CC BY-SA 2.5
2010-11-16T06:43:07.117Z
@Michael: no problem. :)
Kaveh
<graph-theory><graph-algorithms>
Tarjan Strongly Connected Components Question
Wesner Moise
# Tarjan Strongly Connected Components Question

(Asked by: username_0 on 2010-11-16)

Below is Tarjan's SCC algorithm as described in wikipedia.
Input: Graph G = (V, E) 
1.  index = 0                                         // DFS node number counter 
2.  S = empty                                         // An empty stack of nodes 
3.  for all v in V do 
4.   if (v.index is undefined)                       // Start a DFS at each node 
5.     tarjan(v)                                     // we haven't visited yet 

6.  procedure tarjan(v) 
7.   v.index = index                                 // Set the depth index for v 
8.   v.lowlink = index                               
9.   index = index + 1 
10.  S.push(v)                                       // Push v on the stack 
11.  for all (v, v') in E do                         // Consider successors of v 
12.    if (v'.index is undefined)                    // Was successor v' visited? 
13.        tarjan(v')                                // Recurse 
14.        v.lowlink = min(v.lowlink, v'.lowlink) 
15.    else if (v' is in S)                          // Was successor v' in stack S? 
16.        v.lowlink = min(v.lowlink, v'.index)      // v' is in stack but it isn't in the dfs tree 
17.  if (v.lowlink == v.index)                       // Is v the root of an SCC? 
18.    print "SCC:" 
19.    repeat 
20.      v' = S.pop                                   
21.      print v' 
22.    until (v' == v)

In line 16, I could not determine why I could or could not replace line 16 with that of line 14. In other words, it seems to me that taking the min(v.lowlink, v'.lowlink) is the proper approach as opposed to min(v.lowlink, v'.index) in the above example. I have seen one other example on the web that mimics the pseudocode above.
I have considered the unusual use of stack S in the algorithm above in which S may contain items from previous "dead" stack frames. These leftover items aren't removed because they are not the roots of their own strongly connected component.

**Tags:** graph-theory, graph-algorithms
> **Comments:**
> **username_1**: Implementation and programming questions like this are more appropriate for StackOverflow, this site is for *theoretical computer science* questions. I also don't see a question in this post. Voting to close as off-topic.  
> **username_2**: I have to agree... I can't find anything concrete in the question that asks about the concepts of the algorithm itself. Instead, just questions about/problems with the implementation... You should consider [StackOverflow](http://stackoverflow.com/)  
> **username_3**: If I understand him correctly, he's unsure if line 16 is correct. That is, he wants to know if one shouldn't put v'.lowlink instead of v'.index for the algorithm to be correct.  
> **username_1**: @Michael: I don't think that is a *theoretical* computer science question (let alone a research-level one, it can be answered by looking at the proof of correctness of the algorithm in textbooks on graph algorithms).  
> **username_3**: @Kaveh: Just wanted to help :) I think proving correctness of algorithms can count as theoretical computer science. But I agree that it is not research-level and could be easily checked (for some people).  Then again, I think time is better spent if one gives a short answer in certain cases rather than to argue if something is "worthy" of an answer :)  
> **username_1**: @Michael: I understand that you want to help, and proving correctness of *algorithms* (not implementations) *can* count as theoretical computer science, but answering this kind of questions can have a longer term effect on the level of question posted on the site. (ps: I am not saying this is not worthy of answering, just saying this is not the right place for this question and StackOverflow is more suitable for it, please see the discussions on the meta about homework questions to understand my point.)  
> **username_1**: @Michael: ps: IMHO it is not a nice practice to post an answer when a question is being closed. In the case you disagree with closing the question, it is nicer to post your opinion as a comment and wait for a decision before posting an answer.  
> **username_3**: @Kaveh: Didn't see the comments when I posted the answer. Just saw the upvotes.  
> **username_1**: @Michael: no problem. :)  

---

## 1 answers

### Answer by username_3 on 2010-11-16. Score: 1

`v.lowlink = min(v.lowlink, v'.index)` in line 16 is indeed correct. For a full proof you can consult Tarjan's original paper which can also be found [here](http://dutta.csc.ncsu.edu/csc791_spring07/wrap/dfs.pdf).

> Robert Tarjan: Depth-first search and
> linear graph algorithms. In: SIAM
> Journal on Computing. Vol. 1 (1972),
> No. 2, P. 146-160.

Completely unrelated to the question, there is an amusing 1983 retrospective by Bob Tarjan [here](http://www.garfield.library.upenn.edu/classics1983/A1983QY47200001.pdf) on the paper cited above.

> **Comments:**
> **username_4**: It actually works fine the other way too. That's because `lowlink` will never point outside of the current SCC. It's reminiscent of Algorithm 3 in https://www.sciencedirect.com/science/article/abs/pii/S0020019015001532?via%3Dihub  

---

