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