我正在寻找在图形上非递归深度优先搜索算法 在帕斯卡尔（德尔福）。

I am searching for a non-recursive depth first search algorithm on graphs in Pascal (Delphi).

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

I need DFS for computing strongly or bi-connected components of large graphs. Currently I am using a recursive variant of the algorithm: http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm

现在的问题是，对于这样的算法，我必须定义一个大量的内存 用于堆叠和使在视窗7之后的问题， 其中，开放而且由于产生多个线程的保存对话框不工作......

The problem is that for such algorithm I must define a large amount of memory to be used for a stack and that makes later problems in Windows 7, where Open and Save Dialogs do not work because of several threads generated....

所以，再一次：我不知道怎么改写的Tarjan DFS算法 无需递归工作。你有什么建议 - 或指向一个非recursice算法深度上图第一搜索？

So again: I do not see how to rewrite the Tarjan DFS algorithm to work without recursion. Do you have any suggestion - or point to a non recursice algorithm for depth first search on graphs?

感谢。

推荐答案

如维基百科上的算法是合理容易进行非递归有一个明确的堆栈。开始接触的（包括在这里以供参考，在维基百科的情况下改变）：

The algorithm as described on Wikipedia looks to reasonably easily be made non-recursive with an explicit stack. Starting out with that (included here for reference, in case Wikipedia changes):

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（）的回归无以复加，因为我们将跳转到它在瞬间。

Step 1: Remove loops containing recursion, adding labels and gotos. This is necessary to make loop variables explicit, savable and restorable (needed during recursion-simulation with stacks). A label needs to be added after tarjan()'s return, as we'll jump to it in a moment.

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：介绍一个堆栈，其中包含所有相关国家用于存储我们的立场和计算在循环中的任何一点，我们可以从递归返回，或开始了在循环顶部

Step 2: Introduce a stack which contains all the relevant state for storing our position and computation in the loop at any point where we may be returning from recursion, or starting out at the top of the loop.

该堆栈：

T = empty // T will be our stack, storing (v, v', succ, succIndex, state)

状态是一个枚举（ TopState ， ReturnedState ）编码过程中的位置。下面是重写使用该协议栈和状态，而不是递归的过程：

state is an enumeration (TopState, ReturnedState) encoding the location in the procedure. Here's the procedure rewritten to use this stack and state rather than recursion:

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：最后，我们需要确保准入条件是正确的，对于顶级code这就要求的Tarjan。可以很容易地通过初始推来完成：

Step 3: Finally, we need to make sure the entry conditions are correct, for the top-level code which calls tarjan. That can easily be done by an initial push:

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)

这也可以通过跳跃完成的，应立即到顶跳。的code，可以进一步清理，或者转换为使用了一段时间或重复循环，以消除一些goto方法等，但在上述应该至少功能上等同的，从而消除了明确的递归。

It could also be done by a jump, jumping immediately to top. The code can be further cleaned up, perhaps converted to use a while or repeat loop to eliminate some of the gotos, etc., but the above should be at least functionally equivalent, eliminating the explicit recursion.