

 This page uses content from Wikipedia. The original article was at Graph. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance)



Tarjan's algorithm is an algorithm in graph theory for finding the strongly connected components of a graph.

It runs in linear time, matching the time bound for alternative methods including Kosaraju's algorithm and the path-based strong component algorithm.

Tarjan's Algorithm is named for its discoverer, Robert Tarjan.



References

 The article on Wikipedia.


with javascript_semantics
constant g = {{2}, {3}, {1}, {2,3,5}, {6,4}, {3,7}, {6}, {5,8,7}}
 
sequence index, lowlink, stacked, stack
integer x
 
function strong_connect(integer n, emit)
    index[n] = x
    lowlink[n] = x
    stacked[n] = 1
    stack &= n
    x += 1
    for b=1 to length(g[n]) do
        integer nb = g[n][b]
        if index[nb] == 0 then
            if not strong_connect(nb,emit) then
                return false
            end if
            if lowlink[nb] < lowlink[n] then
                lowlink[n] = lowlink[nb]
            end if
        elsif stacked[nb] == 1 then
            if index[nb] < lowlink[n] then
                lowlink[n] = index[nb]
            end if
        end if
    end for
    if lowlink[n] == index[n] then
        sequence c = {}
        while true do
            integer w := stack[$]
            stack = stack[1..$-1]
            stacked[w] = 0
            c = prepend(c, w)
            if w == n then
                emit(c)
                exit
            end if
        end while
    end if
    return true
end function
 
procedure tarjan(sequence g, integer emit)
    index   = repeat(0,length(g))
    lowlink = repeat(0,length(g))
    stacked = repeat(0,length(g))
    stack = {}
    x = 1
    for n=1 to length(g) do
        if index[n] == 0
        and not strong_connect(n,emit) then
            return
        end if
    end for
end procedure
 
procedure emit(object c)
-- called for each component identified.
-- each component is a list of nodes.
    ?c
end procedure
 
tarjan(g,emit)
