使用BFS的2個節點之間的路徑

我已經編寫了一個函數，用於計算使用BFS是否可以從源頂點到達目標頂點。現在我需要跟蹤我用來達到頂點的路徑。我想這應該是一個小小的調整，我們可以將節點添加到我的路徑數組列表中。有人請幫助我。使用BFS的2個節點之間的路徑

public Boolean isReachable(Node destination) { 
    ArrayList<Node> visited = new ArrayList<>(); 
    LinkedList<Node> queue = new LinkedList<>(); 
    ArrayList<Node> path = new ArrayList<>(); 
    queue.add(this); 

    while (queue.size() != 0) { 
     Node source = queue.poll(); 

     for (Node node : source.adjacentNodes) { 
      if (node.equals(destination)) 
       return true; 

      if (!visited.contains(node)) { 
       visited.add(node); 
       queue.add(node); 
      } 

     } 
    } 
    return false; 
}

來源

2016-03-01 Ritabrata

可能重複[只返回實際最短路徑中的頂點]（http://stackoverflow.com/questions/5463505/returning-only-the-vertices-in-act-shortest-path） –

BFS缺少兩個部分。 BFS用於查找節點之間的路徑，但它也嘗試查找最短路徑（但僅查找它搜索的節點），因此通常涉及成本值。既然你只關心節點是否連接，那麼你就不需要這個成本值。

缺少的第二部分是跟蹤通向隊列中當前節點的父節點。看到這裏寫的僞代碼：https://en.wikipedia.org/wiki/Breadth-first_search請注意他們對n.parent和n.distance的使用。

跟蹤另一個數據結構中當前節點的父引用，或者添加一個指向Node節點對象內父節點的指針。然後，一旦當前節點等於目標節點，則可以將父節點指針向後跟隨到起始節點。這將爲您提供從完成節點到開始節點的完整路徑。

如果你想從開始到完成的路徑，你需要遍歷父節點並將它們的引用存儲在列表或其他東西中，並在完成時反轉列表。

來源

2016-03-01 20:49:16 Tansir1

所以你得到了你的bfs算法，但無法檢索到實際的路徑。您只需搜索相同的問題是否已被回答before。

來源

2016-03-10 16:02:01 Bazz

使用BFS的2個節點之間的路徑

回答

相關問題