0

自从我接触 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 个完全不同的代码完成，我会更好地理解它.

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

4

4 回答 4

5

深度优先和广度拳头之间的主要区别在于您探索“前沿”中节点的顺序（您尚未探索的节点列表）。

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

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

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

于 2011-10-13T19:47:05.037 回答
2

您必须将q.add(node)（在列表末尾添加）替换为q.add(0, node)（在开头添加）。基本上，使用 astack而不是 a queue。

显然，您必须使用List界面而不是使用界面Queue来访问LinkedList.

于 2011-10-13T19:38:54.067 回答
1 
Deque<Node> q = new LinkedList<Node>();

使用popandpush代替removeandadd

基本上从您添加的同一侧删除（正常remove并且add是 LIFO 队列基本操作）深度首先使用 FIFO 堆栈

和其他搜索算法基本相同，但使用不同类型的队列（例如，eager search 使用最简单的下一步）

于 2011-10-13T19:40:31.943 回答
0

Queue将and替换LinkedList为Stack, addwith push, and removewithpop

于 2011-10-13T19:44:24.263 回答