java - 在 Java 中将广度优先搜索转换为深度优先搜索

Question

我已经有很长时间没有接触 Java 了，所以这个问题看起来很奇怪。目前有我在 StackOverflow 上找到的这个广度优先搜索代码，我已经修改了它，但我会在这里发布原始代码。

public List<Node> getDirections(Node start, Node finish){
    List<Node> directions = new LinkedList<Node>();
    Queue<Node> q = new LinkedList<Node>();
    Node current = start;
    q.add(current);
    while(!q.isEmpty()){
        current = q.remove();
        directions.add(current);
        if (current.equals(finish)){
            break;
        }else{
            for(Node node : current.getOutNodes()){
                if(!q.contains(node)){
                        q.add(node);
                }
            }
        }
    }
    if (!current.equals(finish)){
        System.out.println("can't reach destination");
}
return directions;
}

我知道那里有其他深度优先搜索算法，但我也被告知可以轻松地将广度优先搜索转换为深度优先搜索，如果对这段代码而不是 2 完成，我会更好地理解它完全不同的代码。

如何将其更改为深度优先搜索？

Answer 1

深度优先和广度优先之间的主要区别在于您在“边界”(您尚未探索的节点列表)中探索节点的顺序。

如果您将当前节点的传出节点添加到该列表的末尾，您将在进入下一个级别之前测试“级别”中的所有可能性(为简化起见，将其想象成一棵树) , 所以你有广度优先搜索。

另一方面，如果您在您之前添加的节点(属于树的“上层”)之前探索新添加的节点(从您当前位置的传出节点)，那么您将首先探索树的深度。

在数据结构方面，您需要 Stack 而不是 Queue，但我认为解释可能会派上用场。