非递归 DFS 实现

Question

最近我需要实现非递归 DFS 作为更复杂算法的一部分，准确地说是 Tarjan 算法。递归实现非常优雅，但不适用于大图。当我实现迭代版本时，我对它最终变得多么不优雅感到震惊，我想知道我是否做错了什么。

迭代 DFS 有两种基本方法。首先，您可以一次将一个节点的所有子节点压入堆栈（这似乎更为常见）。或者你可以只推一个。我将专注于第一个，因为这似乎每个人都是这样做的。

我在这个算法上遇到了各种问题，最终我意识到要高效地完成它，我不需要 1 个，不是 2 个，而是 3 个布尔标志（我不一定意味着您需要三个显式布尔变量，您可能会间接存储信息通过变量的特殊值，通常是整数，但您需要以一种或另一种方式访问​​这 3 条信息。这三个标志是：1）已访问。这是为了防止孩子被非常冗余地推入堆栈。2）完成。防止同一节点的冗余处理。3) 升序/降序。指示子项是否已被推入堆栈。伪代码如下所示：

while(S)
    if S.peek().done == True
        S.pop()
        continue

    S.peek().visited = True

    if S.peek().descending == True
        S.peek().descending = False
        for c in S.peek().children
            if c.visited == False
                S.push(c)
        doDescendingStuff()    
    else
        w = S.pop()
        w.done = True
        doAscendingStuff()

一些注意事项：1）从技术上讲，您不需要升/降，因为您可以只查看孩子是否都完成了。但它在密集图中效率很低。

2），主要问题：访问/完成的事情似乎没有必要。这就是为什么（我认为）你需要它。在访问堆栈之前，您无法标记访问过的事物。如果这样做，您可能会以错误的顺序处理事情。例如，假设 A 链接到 B 和 C，B 链接到 D，D 链接到 C。然后从 A，您将 B 和 C 压入堆栈。从 B 将 D 压入堆栈……然后呢？如果在将它们压入堆栈时标记已访问的事物，则不会在此处将 C 压入堆栈。但这是错误的，应该从 D 访问 C，而不是从图中的 A 访问（假设 A 在 C 之前访问 B）。因此，在处理它们之前，您不会标记访问过的事物。但是，您将在堆栈上有两次 C。所以你需要另一个标志来表明你已经完成了它，所以你不会第二次处理 C。

我不知道如何避免所有这一切以拥有一个完美正确的非递归 DFS，该 DFS 支持缠绕和展开的动作。但本能地感觉很粗糙。有没有更好的办法？我在网上咨询的几乎每个地方都真正掩盖了如何实际实现非递归 DFS，说它可以完成并提供一个非常基本的算法。当算法是正确的（就正确支持到同一节点的多条路径而言）时，这种情况很少见，它很少能正确支持在缠绕和展开上做事。

Answer 1

我认为最优雅的基于堆栈的实现将在堆栈上拥有子级的迭代器，而不是节点。将迭代器视为在其子节点中存储节点和位置。

while (!S.empty)
  Iterator i = S.pop()
  bool found = false
  Iterator temp = null
  while (i.hasNext())
    Node n = i.next()
    if (n.visited == false)
      n.visited = true
      doDescendingStuff(n)
      temp = n.getChildrenIterator()
      break
  if (!i.hasNext())
    doAscendingStuff(i.getNode())
  else
    S.push(i)
  if (temp != null)
    S.push(temp)

上述可以通过将节点和位置分离到2个堆栈来优化ito存储空间。