深度优先搜索在Java中的递归实现

Question

public boolean recursiveDFS(String start, String end){
  clearAll();
  Vertex source = vertexMap.get(start);
  Vertex dest = vertexMap.get(end);
  clearAll();

  return recursiveDFShelper(source,dest);
}

private boolean recursiveDFShelper(Vertex sor, Vertex des){
  if (!sor.name.equals(des.name)){
    sor.setVisited(true);
    Iterator<Edge> it = sor.adj.iterator();

    while (it.hasNext()){
      Vertex v = it.next().target;

      if(!v.isVisited){
        sor.prev=v;
        recursiveDFShelper(v, des); 
      }
    }
    return false;
  }
  else 
    return true;
}

public boolean recursiveDFS(String start, String end){
        clearAll();
        Vertex source = vertexMap.get(start);
        Vertex dest = vertexMap.get(end);
        clearAll();

        return recursiveDFShelper(source,dest);

    }

    private boolean recursiveDFShelper(Vertex sor, Vertex des){
        //System.out.println(sor.name);

        if (!sor.name.equals(des.name)){
        sor.setVisited(true);
        System.out.println(sor.adj);
        Iterator<Edge> it = sor.adj.iterator();
        while (it.hasNext()){
            Vertex v = it.next().target;
            if(!v.isVisited){
                v.prev=sor;
                System.out.printf("prev of %s is %s\n",sor,sor.prev);
                return recursiveDFShelper(v, des);  
                }
            }
        //System.out.println("returning false");
        return false;
        }
        else {
           System.out.println("returning true");
           return true;
        }
        }

A B
B C
C D
A E
E D 

Answer 1

你需要改变

return recursiveDFShelper(v, des);

到

if(recursiveDFShelper(v, des)) {
  return true;
}

否则，您总是在第一次递归调用之后从循环返回。但是，如果递归没有找到元素，则需要继续搜索。另一方面，如果在递归调用中找到了元素，则希望停止搜索。