非递归DFS实现

Question

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

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

我遇到了各种问题，最终我意识到要高效地完成它，我需要不是1个、不是2个，而是3个布尔标志（我不一定意味着您需要三个显式布尔变量，您可以通过通常为整数的变量的特殊值间接存储信息，但您需要以某种方式访问这3个信息。这三个标志是：1）visited。这是为了防止子节点被非常冗余地推入堆栈。2）Done。防止对同一节点进行冗余处理。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访问C（假设A先访问B再访问C）。因此，您不能将元素标记为已访问，直到您对它们进行处理。但是，这样一来，您将在栈中有两个C。因此，您需要另一个标志来显示您已经完全完成了它，以便您不会第二次处理C。

我不知道如何避免所有这些问题，以实现完全正确的非递归DFS，该算法支持绕组和展开操作。但本能地感觉这种方法很复杂。有更好的方法吗？我咨询的几乎每个在线位置都过分简化了如何实际实现非递归DFS，只是提供了一个非常基本的算法。当算法正确时（在支持到同一节点的多条路径方面），这种情况很少发生，很少支持同时进行绕组和展开操作。

- Nir Friedman

---

我没有做过很多这样的问题，但我发现基于栈的递归问题解决方案通常很混乱。我只是很高兴它能够工作。 - Bernhard Barker

我真的不明白为什么你需要visited + done（只需用if S.peek().visited == True替换if S.peek().done == True即可）。在你的例子中，你不会处理两次C，因为当从D处理C时，你会将visited = True。 - Bernhard Barker

我可以问一下，你为什么想要避免递归？许多现代CPU都有优化功能，使得某些递归算法的性能优于它们的非递归对应算法。 - 500 - Internal Server Error

Dukeling，如果你只在那个点将 visited 设置为 True，那么你实际上会遇到无限循环。在我的算法中，只有在升序时才将 done 设置为 True，因此如果你只在那个点将 visited 设置为 True，并且图中存在一个回路，你将不断地将东西加载到堆栈中（因为只有当所有子代都升序时，它们的子代才被标记为 visited，但是它们的子代无法升序直到它们的子代升序……等等）。 - Nir Friedman

500，问题不在于速度，而在于存储。如果您有一个显式的堆栈，那么您可以轻松地拥有与RAM大小相等的深度。递归的最大堆栈大小要小得多，我听说过像8mb这样的数字。像Python这样的语言具有默认的最大递归深度为1000（可以更改）。对于DFS，您的最大堆栈大小通常是图中节点的数量，例如10,000并不特别大。而在归并排序中，您保证最大递归深度为log（n），其中n是已排序数组的大小。所以您是安全的。 - Nir Friedman

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)

可以通过将节点和位置分别存储在两个栈中来优化上述内容的存储空间。

- Bernhard Barker

---

这是一个相当不错的想法。按照给定的方式，我不确定它如何处理展开阶段。由于您只是在推送迭代器，因此只能在给定时间访问子级。当您发现迭代器没有更多子级时，您需要访问原始节点。但是，我认为如果您将节点本身推入，但使用节点的迭代器，则可以很好地完成此操作。不过，归根结底，这甚至会换取稍微更快/更优雅的存储。递归地，您不需要任何这些东西。难道没有更好的方法吗？ - Nir Friedman

编辑。@Nir，考虑一下你的算法，它将给定节点的所有（未访问过的）子节点推入堆栈，但是使用此算法时，你只需将迭代器推入堆栈即可，因此可能需要更少的存储空间。递归算法基本上执行相同的操作（尽管程序员不必处理它）-在每个递归步骤中，您会存储所有局部变量，这至少包括一个节点和子节点数组中的位置。 - Bernhard Barker

处理间接引用有点棘手，但似乎迭代器仍然占用更多空间。无论如何，您必须已经读取了节点和指向它们子节点的指针列表。无论如何，堆栈只是存储指针。但是迭代器本身是另一个在我的代码中不需要的指针。基本上，迭代器是恢复我用于在中间加载子项的for循环的一种方式。因此，它不可能比整数（超过3位）少存储，实际上可能存储2个指针和一个整数（开始，当前，开始+大小）。 - Nir Friedman

Answer 2

你的代码没有完全模拟递归深度优先搜索实现时发生的情况。 在递归深度优先搜索实现中，每个节点在任何时间只出现一次在栈中。

Dukeling提供的解决方案是迭代地执行它。基本上，你只需要一次将一个节点推入栈中，而不是一次性推入所有节点。

你断言这需要更多的存储空间是错误的：使用你的实现，一个节点可以在栈中多次出现。事实上，如果从非常密集的图（所有顶点的完全图）开始，这种情况将会发生。 使用Dukeling的解决方案，栈的大小为O（顶点数）。使用你的解决方案，它是O（边数）。

- Emmanuel Jeandel

Answer 3

算法 BFS(G, v)

enqueue(Q, v)
mark v as visited

while Q is not empty do
    let w = front(Q)
    visit(w)
    dequeue(Q)

    for each vertex u adjacent to w do
        if u is not marked
            enqueue(Q, u)
            mark u as visited

深度优先搜索算法（DFS）(G, v)

push(S, v)
mark v as visited
visit(v)

while S is not empty do
    let w = top(S)
    pop(S)

    find the first umarked vertex u that is adjacent to w 

    if found such vertex u
        push(S, u)
        mark u as visited
        visit(u)

    else if not found such vertex u
        pop(S)

- frankshong

Answer 4

这里有一个链接，展示了使用递归和非递归方法进行深度优先搜索，并计算发现时间和完成时间的Java程序，但没有边标记。

    public void DFSIterative() {
    Reset();
    Stack<Vertex> s = new Stack<>();
    for (Vertex v : vertices.values()) {
        if (!v.visited) {
            v.d = ++time;
            v.visited = true;
            s.push(v);
            while (!s.isEmpty()) {
                Vertex u = s.peek();
                s.pop();
                boolean bFinished = true;
                for (Vertex w : u.adj) {
                    if (!w.visited) {
                        w.visited = true;
                        w.d = ++time;
                        w.p = u;
                        s.push(w);
                        bFinished = false;
                        break;
                    }
                }
                if (bFinished) {
                    u.f = ++time;
                    if (u.p != null)
                        s.push(u.p);
                }
            }
        }
    }
}

完整的源代码在这里。此外，这是一个很好的视频，解释了DFS。

- getsuha

Answer 5

Robert Sedgewick的cpp算法书讲述了一种特殊的栈，它只保留一份项目的副本，并忘记旧的副本。对于如何实现这一点并不完全确定，但它消除了栈中存在多个项目的问题。

- Thusitha

Answer 6

简而言之，您不需要超过一个标志。

实际上，您可以通过显式地执行编译器在运行时堆栈中执行的操作，将递归DFS转换为迭代。该技术使用goto模拟调用和返回，但这些可以转换为更易读的循环。我将使用C进行工作，因为您实际上可以编译中间结果：

#include <stdio.h>
#include <stdlib.h>
#define ARITY 4

typedef struct node_s {
  struct node_s *child[ARITY];
  int visited_p;
} NODE;

// Recursive version.
void dfs(NODE *p) {
  p->visited_p = 1;
  for (int i = 0; i < ARITY; ++i)
    if (p->child[i] && !p->child[i]->visited_p)
      dfs(p->child[i]);
}

// Model of the compiler's stack frame.
typedef struct stack_frame_s {
  int i;
  NODE *p;
} STACK_FRAME;

// First iterative version.
void idfs1(NODE *p) {
 // Set up the stack.
 STACK_FRAME stack[100];
 int i, sp = 0;
 // Recursive calls will jump back here.
 start:
  p->visited_p = 1;
  // Simplify by using a while rather than for loop.
  i = 0;
  while (i < ARITY) {
    if (p->child[i] && !p->child[i]->visited_p) {        
      stack[sp].i = i;   // Save params and locals to stack.
      stack[sp++].p = p;
      p = p->child[i];   // Update the param to its new value.
      goto start;        // Emulate the recursive call.
      rtn: ;             // Emulate the recursive return.
    }
    ++i;
  }
  // Emulate restoring the previous stack frame if there is one.
  if (sp) {
    i = stack[--sp].i;
    p = stack[sp].p;
    goto rtn;   // Return from previous call.
  }
}

现在对代码进行一些“代数”操作，开始摆脱goto。

void idfs2(NODE *p) {
 STACK_FRAME stack[100];
 int i, sp = 0;
 start:
  p->visited_p = 1;
  i = 0;
  loop:
  while (i < ARITY) {
    if (p->child[i] && !p->child[i]->visited_p) {
      stack[sp].i = i;
      stack[sp++].p = p;
      p = p->child[i];
      goto start;
    }
    ++i;
  }
  if (sp) {
    i = stack[--sp].i + 1;
    p = stack[sp].p;
    goto loop;
  }
}

不断变革，我们最终到达这里：

void idfs3(NODE *p) {
  STACK_FRAME stack[100];
  int i, sp = 0;
  p->visited_p = 1;
  i = 0;
  for (;;) {
    while (i < ARITY) {
      if (p->child[i] && !p->child[i]->visited_p) {
        stack[sp].i = i; 
        stack[sp++].p = p;
        p = p->child[i];
        p->visited_p = 1;
        i = 0;
      } else {
        ++i;
      }
    }
    if (!sp) break;
    i = stack[--sp].i + 1; 
    p = stack[sp].p;
  }
}

这很好。还有一个可选的“polish”步骤。我们可以最初将根节点推入堆栈，以简化外部循环：

void idfs3(NODE *p) {
  STACK_FRAME stack[100];
  p->visited_p = 1;
  stack[0].i = 0
  stack[0].p = p;
  int sp = 1;
  while (sp > 0) {
    int i = stack[--sp].i; 
    p = stack[sp].p;
    while (i < ARITY) {
      if (p->child[i] && !p->child[i]->visited_p) {
        stack[sp].i = i + 1; 
        stack[sp++].p = p;
        p = p->child[i];
        p->visited_p = 1;
        i = 0;
      } else {
        ++i;
      }
    }
  }
}

现在很明显，您确实正在使用一堆迭代器：指向节点的指针和反映搜索该节点子项当前进度的索引。使用像Java这样的语言，我们可以使其明确化。（缺点是在处理子项时失去了对父项的访问权限，这可能在某些情况下是一个问题。）

在这里，我将使用单独的集合来保存已访问的节点。这更可取，因为它使得多个搜索和部分搜索变得更加简单。

void search(Node p) {
  Set<Node> visited = new HashSet<>();
  Deque<Iterator<Node>> stack = new ArrayDeque<>();
  visited.add(p); // Visit the root.
  stack.push(p.children.iterator());
  while (!stack.isEmpty()) {
    Iterator<Node> i = stack.pop(); // Backtrack to a child list with work to do.
    while (i.hasNext()) {
      Node child = i.next(); 
      if (!visited.contains(child)) {
        stack.push(i);  // Save progress on this child list.
        visited.add(child); // Descend to visit the child.
        i = child.children.iterator(); // Process its children next.
      }
    }
  }
}

作为最后的微小优化，您可以跳过将耗尽的迭代器推入堆栈（在 C 中，即 child 数组末尾的 i 值），因为它们在弹出后只是被忽略。

void search(Node p) {
  Set<Node> visited = new HashSet<>();
  Deque<Iterator<Node>> stack = new ArrayDeque<>();
  visited.add(p); // Visit the root.
  if (!p.children.isEmpty()) stack.push(p.children.iterator());
  while (!stack.isEmpty()) {
    Iterator<Node> i = stack.pop(); // Backtrack to a child list with work to do.
    while (i.hasNext()) {
      Node child = i.next(); 
      if (!visited.contains(child)) {
        if (i.hasNext()) stack.push(i);  // Save progress on this child list.
        visited.add(child); // Descend to visit the child.
        i = child.children.iterator(); // Process its children next.
      }
    }
  }
}

- Gene

Answer 7

为了使用堆栈进行深度优先遍历，从堆栈中弹出一个节点（记得将初始节点推入堆栈），并检查它是否已经被访问。如果已经访问过，则忽略并弹出下一个节点，否则输出弹出的节点，标记为已访问，并将其所有邻居推入堆栈。重复此操作直到堆栈为空。

- newbie

---

你没有解决问题，挑战在于正确处理卷绕和展开，而你根本没有讨论这个方面。在递归实现中，你可以通过在递归调用之前或之后放置代码来控制这种卷绕/展开。在你的实现中，根节点首先被处理。那么展开呢？在递归实现中，最后运行的代码是在根节点的递归调用之后的代码。在你的实现中，无法在结束时对根节点调用代码。 - Nir Friedman