深度优先搜索从源到目的路径的递归实现

Question

我有这段工作代码，用于非递归地查找源到目标之间的路径。我想实现递归，但我有困难如何做到这一点。

这是我的非递归实现的代码

public boolean depthFirstSearch(String name1, String name2){
        Vertex source = vertexMap.get(name1);
        Vertex dest = vertexMap.get(name2);
        clearAll();

        Stack<Vertex> stack = new Stack<Vertex>();
        source.setVisited(true);
        stack.push(source);

        while(!stack.isEmpty()){
            source = stack.peek();
            System.out.println(source.name);
            if (dest.name.equals(source.name))
                return true;
            Vertex v = adjacentUnvisitedVertex(source);
            if (v!=null){
                v.setVisited(true);
                v.prev=source;
                stack.push(v);
            }
            else stack.pop();   
        }
        if (!source.name.equals(dest.name)){
            System.out.println("destination cannot be reached");
            return true;
        }
        else return false;
    }

    private Vertex adjacentUnvisitedVertex(Vertex v){

        for (Edge e : v.adj){
            if (!e.target.isVisited){
                return e.target;
            }
        }

       return null;
    }

static void dfs (Graphnode n) {
   n.setVisited( true );
   Iterator it = n.getSuccessors().iterator();
   while (it.hasNext()) {
      Graphnode m = (Graphnode)it.next();
      if (! m.getVisited()) dfs(m);
   }
}

我想实现在两个节点A和B之间寻找路径，所以dfs将采用两个节点，递归地寻找之间的路径。

谢谢

Answer 1

堆叠。push（）的地方似乎是递归调用的自然位置。pop（）可能对应于返回结果为false。

但是，将递归的dfs()函数转换为您需要的函数可能更简单：

>

将dfs()转换为目标数据结构(graphnode->vertex，iterator...->，，，...->while(...)等）。检查它是否与system.out.println()一起工作。这可能是最难的部分。如果您在这里遇到困难，请在这里发布输出。

只需添加dest参数并检查节点是否匹配（在本例中返回true，否则在循环后返回false)。确保在循环中检查递归DFS()调用的结果，如果找到了元素，则返回true。