algorithm - Delphi 图形的非递归深度优先搜索

Question

我正在图上搜索非递归深度优先搜索算法在 Pascal (Delphi) 中。

我需要 DFS 来计算大型图的强连接或双连接组件。目前我正在使用算法的递归变体:http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm

问题是对于这样的算法我必须定义大量的内存用于堆栈，这会在 Windows 7 中产生后续问题，由于生成了多个线程，打开和保存对话框不起作用....

再说一遍:我看不出如何重写 Tarjan DFS 算法无需递归即可工作。你有什么建议-或指出用于图深度优先搜索的非递归算法？

谢谢。

Answer 1

维基百科上描述的算法看起来很容易通过显式堆栈变得非递归。从那开始(包括在这里以供引用，以防维基百科发生变化):

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 等，但以上至少在功能上应该是等效的，消除了显式递归。