我正在图上搜索非递归深度优先搜索算法 在 Pascal (Delphi) 中。
我需要 DFS 来计算大型图的强连接或双连接组件。 目前我正在使用算法的递归变体:http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm
问题是对于这样的算法我必须定义大量的内存 用于堆栈,这会在 Windows 7 中产生后续问题, 由于生成了多个线程,打开和保存对话框不起作用....
再说一遍:我看不出如何重写 Tarjan DFS 算法 无需递归即可工作。你有什么建议- 或指出用于图深度优先搜索的非递归算法?
谢谢。
最佳答案
维基百科上描述的算法看起来很容易通过显式堆栈变得非递归。从那开始(包括在这里以供引用,以防维基百科发生变化):
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 步:删除包含递归的循环,添加标签和 goto。这是使循环变量显式、可保存和可恢复所必需的(在使用堆栈进行递归模拟期间需要)。在 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 循环来消除一些 goto 等,但以上至少在功能上应该是等效的,消除了显式递归。
关于algorithm - Delphi 图形的非递归深度优先搜索,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/3747313/