Step through of Tarjan's algorithm

67 Views Asked by At

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 :)

Image of Tarjan's algorithm

Next step of the algorithm

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)...

0

There are 0 best solutions below