1

这是我使用深度优先搜索实现图的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;
    }
4

1 回答 1

2

问题：在你的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!
        }
    }
}
于 2013-03-14T21:32:55.207 回答