DFS算法正在从右向左搜索

我已经编写了深度优先搜索算法，但是它从树的右侧向左搜索。我可以从代码中看到它为什么这样做，但我无法想出一个解决方案来更改它，以便从左到右进行搜索。DFS算法正在从右向左搜索

public class DFS { 

    public LinkedList<Node> search(Node root, Node target) {  
     LinkedList<Node> open = new LinkedList<>(); 
     LinkedList<Node> closed = new LinkedList<>(); 

     open.addLast(root); 
     while (!open.isEmpty()) { 
      Node current = open.removeFirst(); 
      if (current.equals(target)) { 
       closed.addLast(current); 
       return closed; 
      } 
      else { 
       ArrayList<Node> children = current.getChildren(); 
       closed.addLast(current); 
       for (Node child : children) { 
        if (!open.contains(child) && !closed.contains(child)) { 
         open.addFirst(child); 
        } 
       } 
      } 
     } 
     return null; 
    } 
}

closed是按访问顺序访问的节点列表。

Node.getChildren()按照添加它们的顺序返回节点子项的ArrayList。

编辑

这里是节点类：

public class Node { 

    private ArrayList<Node> children; 
    private String name; 

    public Node(String name){ 
     children = new ArrayList<Node>(); 
     this.name = name; 
    } 

    public ArrayList<Node> getChildren(){ 
     return new ArrayList<Node>(children); 
    } 

    public Node addChild(Node child){ 
     children.add(child); 
     return child; 
    } 

    public void removeChild(Node child){ 
     children.remove(child); 
    } 

    public String getName() { 
     return name; 
    } 

    public boolean equals(Node other){ 
     return (this.getName().compareTo(other.getName())==0); 
    } 
}

来源

2016-09-27 KOB

你为什么要做'children.remove（child）'，特别是在'children'循环中？ – user2357112

既然你指出了，我不知道它的目的是什么！基本上我只是想放弃那个节点。我现在将编辑我的代码 – KOB

@ user2357112固定。 – KOB

简单的回答“如何避免从右到左”的问题是：

  ArrayList<Node> children = current.getChildren(); 
      closed.addLast(current); 
      // *** Not like this *** 
      // for (Node child : children) { 
      // if (!open.contains(child) && !closed.contains(child)) { 
      //  open.addFirst(child); 
      // } 
      //} 
      // **** But like this **** 
      for(int i=children.size()-1; i>=0; i--) { 
       Node child=children.get(i); 
       if (!open.contains(child) && !closed.contains(child)) { 
        open.addFirst(child); 
       } 
      } 
      // If you are **absolutely** sure your structure is a 
      // Tree (thus, no cycles) then testing against 
      // open/closed is unnecessary and the code can be simplified: as 
      // open.addAll(0, children);

您ALGO反正是有缺陷的：有没有规定到饱和/丢弃在没有树一个下降通道结果（你永远不会从closed中删除） - 但这不在你的问题的范围之内。

来源

2016-09-27 22:08:14

这完美的工作，我现在也明白了为什么通过在纸上写出一个测试用例。谢谢。该算法作为伪代码给予我们，并且该任务要求编写一个测试类，该类指出是否可以在目标节点上找到路径 - 我认为这是您指出的内容的保护。我们刚刚开始使用这些搜索算法，因此在这种情况下可能尽可能简单。 – KOB

虽然我的答案是从“访问顺序”的角度出发的，但请注意，您已关闭的列表不会包含从根开始的下降路径，而是包含您访问过的所有节点，直到找到答案 - 包括失败的分支*。如果分配要求您返回实际的“根路径”，则您仍有工作要做。 –

我意识到这一点，但分配的范围要求打印在目标节点之前访问过的所有节点。谢谢你的帮助 – KOB

如果你真的DFS依赖于方向，扭转你的孩子，或addfirst仅代替addlast仅？

来源

2016-09-27 21:35:40 Jaleks

的getChildren有1..1

元素然后你有一个堆栈“开放”，从中你在每次执行主循环时弹出的第一个元素。

通过将孩子推到堆栈的前面（addFirst）来填充该堆栈，然后对于1..n以n..1结尾（插入1，现在是第一个，插入2，现在是第一个，1是第二个，依此类推）。

弹出从最后一个索引打开，或将孩子推到堆栈的末尾，它应该工作，除非getChildren没有按照您声明的顺序返回。

来源

2016-09-27 21:36:51 gia

在编写这个DFS算法之前，我写了一个BFS，其中唯一的区别就是你提出的解决方案。从最后一个索引弹出创建一个BFS算法。我测试过'getChildren（）'，它确实按照正确的顺序返回列表。 – KOB

是的，你一直在编辑你的问题，代码会改变每次订购 – gia

DFS算法正在从右向左搜索

回答

相关问题