java深度优先搜索

Question

这是我使用深度优先搜索来实现图的可达（）。它寻找从顶点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! 
     } 
    } 
}