java 深度优先搜索

Question

这是我使用深度优先搜索对图的reachable() 的实现。它寻找从顶点 1 (v1) 到另一个顶点 (v2) 的可能路径 我得到的结果有些是正确的，有些是错误的。我已经尝试了很多方法来调试，但我无法找出问题所在。任何帮助表示赞赏。谢谢

public boolean isReachable(V v1, V v2) {
            Stack<V> path = new Stack<V>();
            return isReachableHelper(v1, v2, path);
        }

}

public boolean isReachableHelper(V v1, V v2, Stack<V> path){
        path.push(v1);
        v1.setVisited(true); //set the vertex as being visited

        if (v1.vertex().equals(v2.vertex())){ //check whether vertex' values are equal
            return true;
        }

            //loop through all vertex that are neighbors of v1
        for (V neighbor : super.neighbors(v1)){ 
            if (!neighbor.visited ){ //if the neighbor is not visited before
                return isReachableHelper(neighbor, v2, path); //recursive call
            }
        }

        path.pop(); //no path was found
        return false;
    }

Answer 1

问题:在 for 循环中，您只扩展第一个未访问的邻居节点，然后立即返回该递归调用的值。也就是说，如果无法通过 v1 的第一个邻居找到路径，您只需“放弃”而不查看其他邻居。

相反，您必须尝试所有个邻居节点，直到找到递归调用返回true的节点。在这种情况下，你已经找到了一条路径，你可以返回true；否则，您的方法会正确地从路径中弹出最后一个节点并返回 false (回溯)。

for (V neighbor : super.neighbors(v1)){ 
    if (!neighbor.visited ){ //if the neighbor is not visited before
        if (isReachableHelper(neighbor, v2, path)) { //recursive call
            return true; // we found a path!
        }
    }
}