algorithm - 深度优先搜索的递归实现以在Java中查找从源到目标的路径

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

虽然这里有一个简单的 DFS 递归实现，它访问所有节点:

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

执行 stack.push() 的地方似乎是递归调用的自然位置。 pop() 应该可能对应于返回 false 作为结果。

但也许将递归的 dfs() 函数转换为您需要的函数会更直接:

1. 将 dfs() 转换为您的目标数据结构(Graphnode -> Vertex，Iterator ... -> while(adjacentUnvisitedVertex(...) 等)。检查它是否适用于 System.out.println()。这可能是最难的部分. 如果您卡在那里，请在此处发布输出。

2. 只需添加一个 dest 参数并检查节点是否匹配(在这种情况下返回 true，在循环后返回 false否则)。确保检查循环中递归 dfs() 调用的结果，如果找到元素则返回 true。