I'm having some trouble wrapping my head around Tarjan's algorithm when I'm going through it step by step. I will post the pseudo code from Wikipedia and tell you where I get lost.
algorithm tarjan is
input: graph G = (V, E)
output: set of strongly connected components (sets of vertices)
index := 0
S := empty stack
for each v in V do
if v.index is undefined then
strongconnect(v)
function strongconnect(v)
// Set the depth index for v to the smallest unused index
v.index := index
v.lowlink := index
index := index + 1
S.push(v)
v.onStack := true
// Consider successors of v
for each (v, w) in E do
if w.index is undefined then
// Successor w has not yet been visited; recurse on it
strongconnect(w)
v.lowlink := min(v.lowlink, w.lowlink)
else if w.onStack then
// Successor w is in stack S and hence in the current SCC
// If w is not on stack, then (v, w) is an edge pointing to an SCC already found and must be ignored
// Note: The next line may look odd - but is correct.
// It says w.index not w.lowlink; that is deliberate and from the original paper
v.lowlink := min(v.lowlink, w.index)
// If v is a root node, pop the stack and generate an SCC
if v.lowlink = v.index then
start a new strongly connected component
repeat
w := S.pop()
w.onStack := false
add w to current strongly connected component
while w ≠ v
output the current strongly connected component
The part that throws me off:
else if w.onStack then
v.lowlink := min(v.lowlink, w.index)
In my head, this makes more sense
v.lowlink := min(v.lowlink, w.lowlink)
I also have an example that indicates what I don't understand, depicted in the picture below.
So it traverses all the way through until (6,6) reaches (2,2), updates its lowlink to (6,2). But then I get really lost whilst backtracking. So now the vertex v is (5,5) right? and vertex w, aka succ(v) is (6,2) right? Since (6,2) has been visited and is on the stack, v.lowlink = min(v.lowlink, w.index). But isn't that min(5, 6) and therefore (5,5) will still be (5,5)? Or am I just completely lost on this one, because in the step through of the algorithm (5,5) becomes (5,2)? I'm thankful for any help on this to nudge me in the right direction :)
EDIT: I think my question got a little bit lost so I posted the next "step" in the step through. I really just need help in understanding the step from (5,5) to (5,2)...

