深度优先搜索的递归实现，以查找Java中两个节点之间的路径 [英] recursive implementation of depth first search to find path between two nodes in Java

问题描述

我正在尝试实现DFS的递归版本，以便在两个节点之间进行深度优先搜索. 这是我的代码.如果存在路径，该方法将返回true，并且它还会更新节点的prev字段以跟踪该路径.我已经使用堆栈实现了这种非递归方式，并且效果很好，这是

I am trying to implement the recursive version of DFS for depth first search between two nodes. Here is my code. The method will return true if there is a path that exists and it also updates the prev field of the node to keep track of the path. I have implemented this non-recursive way using stacks and it works fine which is here.. This one is not working. That is it is not giving me the path from Node A to Node B. It always seem to return false.

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

经过以下建议，我有了这段代码

After below suggestions, I have this code

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 

它能够找到从A到D的正确路径，但是从A到E却失败，而这仅是一个节点.

it is able to find the correct path from A to D, but fails from A to E which is just one node away.

推荐答案

您需要更改

return recursiveDFShelper(v, des);

到

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

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

Otherwise, you always return from the loop after the first recursive call. But you need to continue searching if the recursion did not find the element. On the other hand, if you have found the element in the recursive call, you want to stop the search.

这篇关于深度优先搜索的递归实现，以查找Java中两个节点之间的路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！