Алгоритм, описанный в Википедии, выглядит довольно легко сделать нерекурсивным с явным стеком. Начиная с этого (включен сюда для справки, в случае изменения Википедии):
Input: Graph G = (V, E)
index = 0 // DFS node number counter
S = empty // An empty stack of node
for all v in V do
if (v.index is undefined) // Start a DFS at each node
tarjan(v) // we haven't visited yet
procedure tarjan(v)
v.index = index // Set the depth index for v
v.lowlink = index // SHOULD BE v.lowlink = MAX_INT?
index = index + 1
S.push(v) // Push v on the stack
for all (v, v') in E do // Consider successors of v
if (v'.index is undefined) // Was successor v' visited?
tarjan(v') // Recurse
v.lowlink = min(v.lowlink, v'.lowlink)
else if (v' is in S) // Was successor v' in stack S?
v.lowlink = min(v.lowlink, v'.index ) // v' is in stack but it isn't in the dfs tree
if (v.lowlink == v.index) // Is v the root of an SCC?
print "SCC:"
repeat
v' = S.pop
print v'
until (v' == v)
Шаг 1: Удалите циклы, содержащие рекурсию, добавление меток и переходов. Это необходимо для того, чтобы сделать переменные цикла явными, сохраняемыми и восстанавливаемыми (необходимо во время симуляции рекурсии со стеками). Метка должна быть добавлена после возврата tarjan(), поскольку мы сразу к ней перейдем.
procedure tarjan(v)
v.index = index // Set the depth index for v
v.lowlink = index // SHOULD BE v.lowlink = MAX_INT?
index = index + 1
S.push(v) // Push v on the stack
succ = all (v, v') in E // Consider successors of v
succIndex = 0 // presume succ is 0-based
loop_top:
if succIndex >= Length(succ) goto skip_loop
v' = succ[succIndex]
if (v'.index is undefined) // Was successor v' visited?
tarjan(v') // Recurse
recursion_returned:
v.lowlink = min(v.lowlink, v'.lowlink)
else if (v' is in S) // Was successor v' in stack S?
v.lowlink = min(v.lowlink, v'.index ) // v' is in stack but it isn't in the dfs tree
succIndex = succIndex + 1
goto loop_top
skip_loop:
if (v.lowlink == v.index) // Is v the root of an SCC?
print "SCC:"
repeat
v' = S.pop
print v'
until (v' == v)
Шаг 2. Представьте стек, который содержит все соответствующие состояния для хранения нашей позиции и вычислений в цикле в любой точке, где мы можем возвращаться из рекурсии или начинать с верхней части цикла.
Стек:
T = empty // T will be our stack, storing (v, v', succ, succIndex, state)
state - это перечисление (TopState, ReturnedState), кодирующее местоположение в процедуре. Вот процедура, переписанная для использования этого стека и состояния, а не рекурсии:
procedure tarjan(v)
while (T is not empty) do
(v, v', succ, succIndex, state) = T.pop
case state of
TopState: goto top
ReturnedState: goto recursion_returned
end case
top:
v.index = index // Set the depth index for v
v.lowlink = index // SHOULD BE v.lowlink = MAX_INT?
index = index + 1
S.push(v) // Push v on the stack
succ = all (v, v') in E // Consider successors of v
succIndex = 0 // presume succ is 0-based
loop_top:
if succIndex >= Length(succ) goto skip_loop
v' = succ[succIndex]
if (v'.index is undefined) // Was successor v' visited?
// instead of recursing, set up state for return and top and iterate
T.push(v, v', succ, succIndex, ReturnedState) // this is where we return to
T.push(v', empty, empty, empty, TopState) // but this is where we go first
continue // continue the while loop at top
recursion_returned:
v.lowlink = min(v.lowlink, v'.lowlink)
else if (v' is in S) // Was successor v' in stack S?
v.lowlink = min(v.lowlink, v'.index ) // v' is in stack but it isn't in the dfs tree
succIndex = succIndex + 1
goto loop_top
skip_loop:
if (v.lowlink == v.index) // Is v the root of an SCC?
print "SCC:"
repeat
v' = S.pop
print v'
until (v' == v)
Шаг 3: Наконец, нам нужно убедиться, что условия входа верны для кода верхнего уровня, который вызывает tarjan. Это легко сделать с помощью начального нажатия:
procedure tarjan(v)
T.push(v, empty, empty, empty, TopState)
while (T is not empty) do
(v, v', succ, succIndex, state) = T.pop
case state of
TopState: goto top
ReturnedState: goto recursion_returned
end case
top:
v.index = index // Set the depth index for v
v.lowlink = index // SHOULD BE v.lowlink = MAX_INT?
index = index + 1
S.push(v) // Push v on the stack
succ = all (v, v') in E // Consider successors of v
succIndex = 0 // presume succ is 0-based
loop_top:
if succIndex >= Length(succ) goto skip_loop
v' = succ[succIndex]
if (v'.index is undefined) // Was successor v' visited?
// instead of recursing, set up state for return and top and iterate
T.push(v, v', succ, succIndex, ReturnedState) // this is where we return to
T.push(v', empty, empty, empty, TopState) // but this is where we go first
continue // continue the while loop at top
recursion_returned:
v.lowlink = min(v.lowlink, v'.lowlink)
else if (v' is in S) // Was successor v' in stack S?
v.lowlink = min(v.lowlink, v'.index ) // v' is in stack but it isn't in the dfs tree
succIndex = succIndex + 1
goto loop_top
skip_loop:
if (v.lowlink == v.index) // Is v the root of an SCC?
print "SCC:"
repeat
v' = S.pop
print v'
until (v' == v)
Это также можно сделать прыжком, сразу прыгнув на top. Код может быть дополнительно очищен, возможно, преобразован для использования цикла while или repeat для устранения некоторых ошибок и т. Д., Но вышеприведенное должно быть по крайней мере функционально эквивалентным, исключая явную рекурсию.