首页 文章

用于递归深度优先搜索以存储路径的额外空间

提问于
浏览 次
5

我使用深度优先搜索来识别有向加权图中的路径，同时重新访问属于循环的节点，并根据行进的总距离设置截止条件，或者从源节点停止 .

据我所知，对于递归，深度优先搜索不需要显式堆栈结构，所以我想知道是否可以通过某种方式在没有显式堆栈的情况下进一步简化我的代码：

public class DFSonWeightedDirectedGraph {

    private static final String START = "A";
    private static final String END = "E";
    private int pathLength = 0;
    private int stops = 0;

    public static void main(String[] args) {
        //this is a directed weighted graph
        WeightedDirectedGraph graph = new WeightedDirectedGraph();
        graph.addEdge("A", "B", 15);
        graph.addEdge("A", "D", 15);
        graph.addEdge("A", "E", 27);
        //(...) more edges added


        Stack<String> visited = new Stack<String>();        
        visited.push(START);

        new DFSonWeightedDirectedGraph().depthFirst(graph, visited);
    }

    private void depthFirst(WeightedDirectedGraph graph, Stack<String> visited) {

        Collection<Map.Entry<String, Integer>> tree_of_children 
            = graph.get_tree_of_children(visited.peek());

        for (Map.Entry<String, Integer> child : tree_of_children) {


            if(pathLength + child.getValue()>= 20){
                continue;
            }       


            visited.push(child.getKey());
            pathLength += child.getValue();
            stops += 1;         

            if (child.getKey().equals(END)) {
                printPath(visited);
            }

            depthFirst(graph, visited); 
            visited.pop();  
            pathLength -= child.getValue();
            stops -= 1; 
        }
    }

    private void printPath(Stack<String> visited) {
        for (String node : visited) {
            System.out.print(node);
            System.out.print(" ");
        }
        System.out.println("[path length: "+pathLength +
                " stops made: " + stops +"]");
    }
}

但是，没有显式堆栈结构的其他递归实现通常会考虑已经访问过的节点，通过将它们着色为白色，灰色或黑色 . 所以，在我允许重访的情况下，需要记录路径，是否需要显式堆栈？感谢您提供更简单的替代方案 .

java algorithm recursion graph depth-first-search

4 回答

  • 0

    您不需要访问过的节点 . 只需将当前子节点传递给递归方法而不是访问节点参数，并使用返回值来传递路径 .

    如果你可以按元素处理path元素，即重写printPath（），以便每个元素可以调用一次，只需要键类型作为返回类型 . 如果要接收整个路径，则需要键值列表作为返回类型 .

    实际上，你是比较接近解决方案的 . 只需使用递归方法调用的调用堆栈来表示路径 .

    回复于
  • 0

    如果必须保存路径，则需要一个数据结构 . 你的筹码还行;你可以用另一种数据结构替换它，但不能摆脱它 .

    如果可以直接打印路径（而不是记录它），则不需要堆栈 . 然后，您可以更改方法签名以获取图形和实际节点（可能还有实际路径长度和“停止”） .

    回复于
  • -1

    只需在节点结构中添加一个额外的字段，即“访问”字段 . 这将是最快的 . 您必须在之后（或在进行搜索之前）取消标记所有节点 .

    或者，只是在哈希表中散列节点的id . 检查比堆栈更快 . 如果您没有节点的id，最好创建一个，以帮助调试，输出等 .

    您确实需要额外的空间，但为每个节点添加布尔字段将需要最小的空间，因为每个节点将为1位，而堆栈的每个节点为1个指针 .

    您实际上并不需要距离截止，因为您正在搜索有限图并且您只访问每个节点一次，因此您将访问N节点图中的大多数N个节点 . 如果您正在搜索无限空间，则需要深度截止，例如在进行状态空间搜索时（例如，prolog解释器搜索证明） .

    回复于
  • 1

    编辑：这个答案完全偏离主题，并根据误解问题发布 .

    您的DFS实施有几个问题 . 是的，它以深度优先的方式访问所有节点，并且它最终设法找到START和END之间的路径，但它不会尝试检查已访问过的节点并且没有真正的原因保留堆栈 . 在循环中不进行无限递归的唯一原因是因为限制了最大路径长度，并且在所有顶点对之间具有多个不同路径的图上仍然需要很长时间 .

    您使用堆栈的唯一方法是传递dfs函数旁边要访问的节点 . 您可以简单地删除堆栈并直接传递节点 .

    所以，而不是

    private void depthFirst(WeightedDirectedGraph graph, Stack<String> visited) {
   ...
   visited.push(child);
   ...
   depthFirst(graph, visited);

    你可以简单地把它写成

    private void depthFirst(WeightedDirectedGraph graph, String node) {
   ...
   //visited.push(child); <-- No longer needed
   ...
   depthFirst(graph, child);

    您正在使用名为“已访问”的数据结构（堆栈），但您不使用它来存储/标记已访问过哪些节点以避免重新访问 .

    您可以修改现有代码，使其具有一个名为visited的Set（使其成为全局/类变量，或者像对堆栈一样通过递归调用传递它），其中保留所有已访问过的节点，并仅在那些节点上调用depthFirst（）尚未进入该集合 .

    这应该使您的代码看起来像这样

    private void depthFirst(WeightedDirectedGraph graph, String node, Set<String> visited) {
   visited.add(node); // mark current node as visited
   ...
   //visited.push(child); <-- No longer needed
   ...
   if (!visited.contains(child)){ // don't visit nodes we have worked on already
      depthFirst(graph, child);
   }

    到目前为止，我的答案是尝试修改您的代码以使其工作 . 但在我看来，你需要更好地掌握DFS究竟是什么以及它是如何运作的 . 阅读任何好的算法/图论理论书的相关章节对你有很大的帮助 . 我会推荐CLRS（它有一个关于简单图遍历的非常好的章节），但任何好书都应该这样做 . 一个简单而正确的递归DFS可以在一个实现更简单的方式使用数组，而不必诉诸堆栈或集合 .

    编辑：我没有提到如何在更换堆栈后检索路径 . 这可以通过使用Map来轻松完成，该Map存储探索时每个节点的父节点 . 可以使用递归printPath（String节点）函数获取路径（如果找到任何路径），该函数打印传递给它的节点并在其父节点上再次调用自身 .

    回复于

相关问题