带BFS的ShortestPath（BreadthFirstSearch）

Question

我想返回图的两个顶点之间的最短路径。我写了一段代码来查找breadthFirstSearch，但我不知道如何修改它以使其返回最短路径。下面是我的广度FirstSearch函数

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