java - 使用 BFS(广度优先搜索)的最短路径

Question

我正在尝试返回图的两个顶点之间的最短路径。我编写了一段代码来查找宽度优先搜索，但我不知道如何修改它以使其返回最短路径。下面是我的 widthFirstSearch 函数

private void breadthFirstSearch(T start,T end){

    Queue<T> queue = new LinkedList<>();
    Set<T> visited = new HashSet<>();
    visited.add(start);
    queue.add(start);
    while(!queue.isEmpty()){
        T v = queue.poll();
            for(int i =0;i<this.keyToVertex.get(v).successors.size();i++){                  if(visited.contains(this.keyToVertex.get(v).successors.get(i).key)){ 
                continue;
            }
            visited.add(this.keyToVertex.get(v).successors.get(i).key);
            queue.add(this.keyToVertex.get(v).successors.get(i).key);
        }

    }       

}

那么我该如何修改它以返回最短路径。

Answer 1

您需要跟踪Queue不仅仅是要检查的值，还有通往该值的路径。所以类型应该不仅仅是 Queue<T>但例如 Queue<LinkedList<T>> .

队列中的第一个值应该是start的单例列表而不仅仅是start .

当您处理队列中的值时，您正在访问的顶点将是队列项目的最后一个元素，并且当您将项目添加到队列时，它应该是当前项目的克隆，以及下一个项目邻居已添加。

类似这样的事情:

Queue<LinkedList<T>> queue = new LinkedList<>();
queue.add(new LinkedList<>(Collections.singleton(start)));

while (!queue.isEmpty()) {
    LinkedList<T> path = queue.poll();
    T v = path.getLast();
    if (v.equals(end)) {
        return path;
    }

    for (int i = 0; i < this.keyToVertex.get(v).successors.size(); i++) {
        T v2 = this.keyToVertex.get(v).successors.get(i).key;
        if (visited.contains(v2)) {
            continue;
        }

        LinkedList<T> path2 = new LinkedList<>(path);
        path2.add(v2);
        queue.add(path2);
        visited.add(v2);
    }
}