ShortestPath with BFS（BreadthFirstSearch）

Question

グラフの2つの頂点間の最短経路を返そうとしています。 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); 
    } 
}