DFS算法是从右向左搜索

Question

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

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() returns 节点子节点按添加顺序排列的 ArrayList。

编辑

这里是节点class:

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

Answer 1

如果你的DFS真的依赖方向，反转你的children，或者addFirst而不是addLast？

Answer 2

getChildren 有元素 1..n

然后你有一个堆栈"open"，每次执行主循环时你都会从中弹出第一个元素。

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

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

Answer 3

对'how to avoid right-to-left'问题的简单回答是：

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

你的算法无论如何都是有缺陷的：没有规定 windup/discard 树中的下降路径未能产生结果（你永远不会从 closed 中删除） - 但这是不对的你的问题范围。

DFS算法是从右向左搜索

DFS algorithm is searching from right to left

java

tree

search

depth-first-search