重新访问树上递归函数 (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

根据你想在树上备份多远，这样的事情应该有效。

DFS 函数 returns 要重试的级别数：

0 照常进行
1 重试同一个节点
2 重试 parent...

代码：

int DFS(node x)
{
    if (some condition)
    {
        // return the number of parent levels you want to back up
        return 2;
    }

    for (int i = 0; i < x.children.size; ++i)
    {
        int redo = DFS(x.children[i]);

        if (redo == 1) {
            // redo == 1 means retry the current node
            --i;
        }
        if (redo > 1) {
        {
            // redo > 1 means retry an ancestor node
            return redo - 1;
        }
    }
    return 0;
}

显然你必须小心你的条件，否则你将陷入无限循环。

有了上面的基本代码，下面的条件就会returnA B C D E C D E F G

boolean retryE = true;

int DFS(node x)
{
    if (x.value == "E" && retryE)
    {
        retryE = false;
        return 2;
    }

    // remaining code as above
}

更新

再看一遍，如果你的评估函数 return 是一个祖先节点而不是多个级别，这可能更接近你最初想要的......如果节点 returned不是当前 child...

的祖先

// returns null to continue DFS, or a node value to repeat from that node
Node DFS(Node x)
{
    Node z = evaluate(x)

    if (z != null)
    {
        return z;
    }

    for (int i = 0; i < x.children.size; ++i)
    {
        Node child = x.children[i];
        Node result = DFS(child);

        if (result != null)
        {
            if (result == child)
            {
                // current child is the one to retry so just
                // decrement the counter to retry it
                --i;
            } else {
                // retry a node but not this child so return it up the stack
                return result;
            }
        }
    }

    return null;
}

更新 2

使用相同的 DFS 函数，考虑这个求值函数，对于 E 和 F 的第一次出现，returns C

boolean retryE = true;
boolean retryF = true;

evaluate(Node x)
{
    if (x.value == "E" && retryE)
    {
        retryE = false;
        return C;
    }
    if (x.value == "F" && retryF)
    {
        retryF = false;
        return C;
    }
    return null;
}

这将使用 --i 递减方法（returning A B C D E - C D E F - C D E F G）正确工作，但如果直接调用 DFS(child) 则不会，除非第二次调用的结果以某种方式处理。

干杯

Answer 2

我将尝试使用全局变量来概述伪代码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 时将相关节点取消标记为未访问。

Answer 3

看到这里我可以看到你使用了一个 void DFS，你的函数没有 returning 任何东西所以你可以使用那个值来检查是否需要重新评估某些东西。

像这样

int DFS(node x)
{
    int ret=0;
    z = evaluate(x);
    // if (z != null) DFS(z) Z could be a node which has been already traversed 
    foreach (node y in c.children)
    {
        ret=DFS(y);
        if(ret==1)
          break;
    }
    if(ret==1)
       DFS(x);

    if(z==(want to reevaluate))
        return 1;
    else
        return 0;
}

现在你可以简单地 return 到 parent 1 如果你想让它重做所有的 DFS children 你可以简单地 return 0如果你想让它继续下去。如果在这种情况下，A returned 1 的任何 children 将重新评估所有 children 和该节点，并且其上方的节点将以与之前相同的方式继续。

所以你 image.If E returns 1 那么所有节点 C,D,E 都将被重新评估。如果您将 return 值固定为 return 距离或其他值，那么这也可以使用变量来完成，您只需要将其地址发送到所有 children 并观察其值。

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

Revisiting some nodes in a recursive function (DFS) over a tree

algorithm

tree

recursion