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! 
     } 
    } 
}