将广度优先搜索转换为深度优先搜索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

Depth first和Breadth拳头之间的主要区别在于您探索"前沿"(您尚未探索的节点列表)中的节点的顺序.

如果将当前节点中的传出节点添加到该列表的末尾,则在进入下一级别之前,您将在"级别"(为简化目的,将其想象为树)中测试所有可能性,因此您有广度优先搜索.

另一方面,如果您在之前添加的节点(属于树的"上层")之前探索新添加的节点(当前位置的传出节点),那么您将成为首先探索树的深度.

在数据结构方面,你需要一个堆栈而不是一个队列,但我认为这个解释可能会派上用场.