algorithm - 非递归 DFS 实现

Question

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

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

我在使用这个算法时遇到了各种问题，最终我意识到要高效地执行它，我需要的不是 1 个，也不是 2 个，而是 3 个 bool 标志(我并不一定意味着你需要三个显式 bool 变量，你可以存储通过通常为整数的变量的特殊值间接获取信息，但您需要以一种或另一种方式访问​​这 3 条信息。这三个标志是:1) 已访问。这是为了防止 child 被非常多余地推到堆栈上。 2)完成。防止对同一节点进行冗余处理。 3) 升序/降序。指示 child 是否已经被插入堆栈。伪代码看起来像这样:

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，说可以做到并提供非常基本的算法。当算法正确时(就正确支持到同一节点的多条路径而言)这种情况很少见，它很少能正确支持在缠绕和展开时做一些事情。

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 个堆栈上来优化 i.t.o 存储空间。