BFS 的最短路径（广度优先搜索）

Question

我正在尝试 return 图形的两个顶点之间的最短路径。我编写了一段代码来查找 breadthFirstSearch，但我不知道如何修改它以使其 return 成为最短路径。下面是我的 breadthFirstSearch 函数

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

    }       

}

那么如何修改为return最短路径。

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

BFS 的最短路径（广度优先搜索）

ShortestPath with BFS (BreadthFirstSearch)

java

shortest-path

breadth-first-search