DFS 递归，重新访问节点，即使在被标记为已访问之后

Question

所以，我一直在尝试运行这个简单的 DFS 代码使用递归，我已经将已经访问的节点标记为已访问，但它再次围绕访问的节点循环，所以我注意到布尔值数组 isVisited 在每个递归步骤中都会再次创建，我无法将数组放在此方法之外的 class 中，并在方法内部使用它。任何帮助，将不胜感激！ :)

private boolean hasRoutesDFS(int start, int end) {
    if (start < 0 || start > graph.size() || end < 0 || end > graph.size())
        return false;
    boolean[] isVisited = new boolean[graph.size() + 1];

    if (start == end)
        return true;
    else{
         isVisited[start]=true;
        System.out.print(start + "->");
        for (int v : graph.getEdge(start)) {
            if (!isVisited[v] ) {
                isVisited[v] = true;
                hasRoutesDFS(v, end);
            }
        }

    }

    return false;
}

编辑：好吧，多亏了答案中提供的技巧，我能够修复代码，现在它似乎也在处理更新的测试用例，但在某种程度上它似乎仍然是错误的，假设我给代码一个图表以下边：
（端点 1）（端点 2）
1 2
1 3
2 3
2 4
3 5
4 5
4 6
5 6

如果我从节点 1 到 5 搜索 DFS，我得到的答案是 1->2->3->5，这是一条有效路径，但可能有更深的 1->2 ->4->6->5 路径也是如此，这不是 DFS 应该做的吗？走完整个深度？

新代码：

private boolean hasRoutesDFS(int start, int end) {
    return hasRoutesDFS(start, end, new boolean[graph.size() + 1]);
}

private boolean hasRoutesDFS(int start, int end, boolean[] isVisited) {
    if (start < 0 || start > graph.size() || end < 0 || end > graph.size()) {
        return false;
    }

    if (start == end) {
        System.out.print(start);
        return true;
    } else {
        isVisited[start] = true;
        System.out.print(start + "->");
        for (int v : graph.getEdge(start)) {
            if (!isVisited[v]) {
                if(hasRoutesDFS(v,end,isVisited))
                    return true;
                hasRoutesDFS(v, end, isVisited);
            }
        }

    }

    return true;
}

Answer 1

使递归函数使用静态数据的标准技巧是将静态数据作为参数传递并从基本签名创建它。

private boolean hasRoutesDFS(int start, int end) {
    return hasRoutesDFS(start, end, new boolean[graph.size() + 1]);
}

private boolean hasRoutesDFS(int start, int end, boolean[] isVisited) {
    if (start < 0 || start > graph.size() || end < 0 || end > graph.size()) {
        return false;
    }

    if (start == end) {
        return true;
    } else {
        isVisited[start] = true;
        System.out.print(start + "->");
        for (int v : graph.getEdge(start)) {
            if (!isVisited[v]) {
                isVisited[v] = true;
                hasRoutesDFS(v, end, isVisited);
            }
        }

    }

    return false;
}

没有以任何方式暗示您的其余代码是正确的（实际上在我看来是错误的）。只是向您展示如何避免在每次调用时创建新数组时遇到的问题。

DFS 递归，重新访问节点，即使在被标记为已访问之后

DFS Recursion, Revisiting nodes, even after being marked as visited

java

recursion

depth-first-search