java - 在 Java 中通过递归调用添加变量无法正常工作

Question

当我偶然发现一个错误时，我在图上实现了一个桥查找算法，其中我的递归调用不能正确求和。

如果您查看函数“root()”中的递归调用，标记为“DOES WORK”的递归调用在终止后将索引为 2 的节点的“cnt”解析为 2(正确答案)，而无法正常工作的递归调用则将“cnt”解析为 4。我已使用调试器尝试查明问题，但问题是我认为我的代码没有任何问题。在某一时刻，递归调用返回 2，节点 2 的“cnt”值应该是 -1，但是添加了错误的代码块后，“cnt”变成了 2，而不是 1。

任何帮助将不胜感激。我不确定这是否是 java、我的 IDE 或我的其他方面的错误。

public class BridgeFind {
    int N;
    Node[] dfsTree;
    boolean[] visited;
    void init() {
        dfsTree = new Node[N];
        for (int i = 0; i < N; i++) {
            dfsTree[i] = new Node();
        }
        visited = new boolean[N];
    }
    int root(int n, int p, int d) {
        visited[n] = true;
        dfsTree[n].d = d;
        for (int ch : dfsTree[n].adj) {
            if (ch != p) {
                if (!visited[ch]) {
                    //DOES NOT WORK
                    dfsTree[n].cnt += root(ch, n, d+1);

                    //DOES WORK
                    int val = root(ch, n, d+1);
                    dfsTree[n].cnt += val;

                } else if (dfsTree[n].d > dfsTree[ch].d){
                    dfsTree[n].cnt++;
                    dfsTree[ch].cnt--;
                }
            }
        }
        return dfsTree[n].cnt;
    }
    static class Node {
        ArrayList<Integer> adj = new ArrayList<>();
        int cnt = 0;
        int d;
    }
    void add(int a, int b) {
        a--;
        b--;
        dfsTree[a].adj.add(b);
        dfsTree[b].adj.add(a);
    }
    void solve() {
        N = 12;
        init();
       add(1, 3);
       add(5, 3);
       add(7, 5);
       add(6, 3);
       add(6, 2);
       add(2, 8);
       add(2, 4);
       add(4, 10);
       add(1, 9);
       add(9, 11);
       add(11, 12);
       add(9, 12);
       add(1, 6);
       add(1, 5);
       add(3, 7);
       add(3, 8);
       root(0, 0, 0);
       visited = new boolean[N];
       System.out.println(dfsTree[2].cnt);
    }
    public static void main(String[] args) {
        BridgeFind next = new BridgeFind();
        next.solve();
    }
}

Answer 1

虽然这两个代码片段表面上看起来很相似，但实际上它们根本没有做同样的事情。

此 block 首先评估 root(ch, n, d+1)(它修改 dfsTree[n].cnt)，然后将返回值添加到 dfsTree[n].cnt 的新值。

int val = root(ch, n, d+1);
dfsTree[n].cnt += val;

另一方面，此行首先捕获 dfsTree[n].cnt 的值，然后评估 root(ch, n, d+1) (这会修改 dfsTree[n].cnt)，将返回值添加到 dfsTree[n].cnt 的原始值中并存储它，这会覆盖调用 root( ch、n、d+1)。

dfsTree[n].cnt += root(ch, n, d+1);

编辑

如果您想要一个不依赖临时变量的单行解决方案，您可以通过编写标准赋值来强制计算顺序。 x += y 是 x = x + y 的简写，但如果您需要先计算 y，则只需将其写为 x = y + x。

例如

dfsTree[n].cnt = root(ch, n, d+1) + dfsTree[n].cnt;

程序输出为2。