algorithm - 重新访问树上的递归函数 (DFS) 中的某些节点

Question

我以深度优先的方式遍历树的节点。假设树如下:

现在，假设我位于节点 E 中，并且在某些情况下我想返回到节点 C 并从那里继续。然后应取消先前的遍历并重新评估节点C、D、E。节点 F 和 G 不应被遍历两次，因为先前的递归导航已被取消!

Usual navigation : A B C D E F G
The desire navigation : A B C D E C D E F G

深度优先遍历的一般代码如下:

void DFS(node x)
{
    z = evaluate(x);
    // if (z != null) DFS(z) 
    // Z could be a node which has been already traversed, 
    // let's suppose it's an ancestor of x

    foreach (node y in c.children)
    {
        DFS(y);
    }
}

请帮助我如何在树中进行这样的导航？

Answer 1

我将尝试使用全局变量cancel来概述伪代码。

boolean cancel = false;

void DFS(node x, parent p)
{
    if(!cancel) {
        foreach (node y in x.children) {
            DFS(y, x);
        }
    } else {
      cancel = false;
      DFS(p, findParent(p));
    }
}

但是，这种方法有一个问题。一旦在 foreach 部分开始遍历，循环内对 DFS 方法的每次后续调用都将从父节点调用 DFS。为了解决这个问题，我建议您使用自己的堆栈来模拟深度优先遍历，而不是采用递归方法。这样，当 cancel 变为 true 时，您可以清除堆栈并确保来自父级的 DFS 调用仅发生一次。希望这有帮助!

以下几行中的某些内容应该有效:

boolean cancel = false;
Stack<Node> s;

void DFSIterative(Node x, Node p) {
    if(cancel) {
        resetDFS(p);
    } else {
        s.push(x);
        while(!s.isEmpty()) {
            x = s.pop();
            p = findParent(x);
            if(cancel) resetDFS;
            else {
                foreach(node y in x.children) {
                    s.push(y);
                }
            }
        }
    }
}

void resetDFS(Node p) {
    s.clear();
    cancel = false;
    DFSIterative(p, findParent(p));
}

我将 findParent() 辅助方法的实现留给您。请注意，您还需要注意将节点标记为已访问，然后在取消 DFS 时将相关节点取消标记为未访问。