我正在嘗試用 Java 撰寫一些 BFS 演算法并在線閱讀我們應該維護類似陣列的東西，prev其中prev[i] = j表明我們之前訪問的節點i是 node j。
所以假設我有這樣一個陣列。如何恢復原來的路徑？有沒有我可以查看的示例代碼？我并沒有真正得到解決方案中的解釋，它似乎只是掩蓋了“回到”源頭的步驟。
uj5u.com熱心網友回復：
廣度優先搜索通常需要一個具有 FIFO 順序的佇列。
以下是一些示例代碼供您使用：
class Node<T> {
Node<T> left;
Node<T> right;
T data;
}
public static void Main(String[] args) {
Node<String> root; // assume this is initialized with plenty of children
Queue<Node<String>> bfs_queue(root);
while(!bfs_queue.empty()) {
Node target = bfs_queue.get();
if(target == null) continue;
// Do something with the data
System.out.println(target.data)
bfs_queue.push(target.left);
bfs_queue.push(target.right);
}
}
如您所見，我們使用佇列為我們提供第一個進入的專案，而對于我們在當前級別的整個范圍內提取的每個專案，我們不斷添加target節點子項以準備搜索下一個級別。
（旁注，上面的代碼是偽 Java 代碼，但足夠接近）
uj5u.com熱心網友回復：
我的理解是您在 BFS 之后填充了一個父陣列。parent 陣列保存節點的父 id，換句話說，就是在當前節點之前訪問過的節點。擁有陣列后，您可以像這樣列印路徑：
void printPath(int[] parent, int i) {
if(parent[i] == -1) {//Root node does not have a parent
return;
} else {
printPath(parent, parent[i]);
System.out.println(i);
}
}
請注意，只有當您使用整數標記/識別圖中的節點時，此表示才會起作用0... |V|。另一種常見的表示是地圖（或字典）。
Map<Node, Node> parentTree
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/336693.html