我正在嘗試解決一個問題，該問題在樹上應用廣度優先搜索演算法和深度優先搜索演算法，并找出這兩種演算法找到的遍歷和最終路徑。
我真正感到困惑的是如何計算這兩條不同的路徑？它們真的不同嗎？
例如，考慮以下樹，
假設我們的起始節點是A，目標節點是H
對于這兩種演算法，我覺得這就是遍歷和最終路徑
- 對于 BFS
遍歷路徑： ABCDEFGH
最終路徑： ACFH
如果這是它的作業原理，那么我怎樣才能找到最終路徑？它很容易找到遍歷的路徑，但找到最終路徑并不那么容易。
相似地，
- For DFS
Traversal Path: A B D E C F G
Final Path: A C F H
Again, how can I extract the Final Path from the Traversal Path for DFS.
This actually gets a bit more complicated. What if my Goal Node is reachable from two sides? How do I find the Final Path in such a scenario?
For example, Consider the following scenario,
Let's say for this case, our Starting Node is A and Goal Node is H, again.
Traversal path is very easy to compute with both BFS and DFS.
But for the Final Path, "H" is reachable from two sides, it is reachable from F and it is also reachable from G
For the DFS, you may write the final path as A C F G because from the F node, we would reach the H first (as G would still be unexplored, however you would still have to extract this Final Path from the Traversal path, which I do not know how to do)
But for BFS, you can not do that. So, what would be my Final Path in this scenario? Should there be two Final Paths in such a scenario?
Can anyone help me out in this please.
uj5u.com熱心網友回復：
一種[多種可能的]方法是維護目標到源節點的映射。每次前進時，記錄哪個源節點進行了該前進。所以，在 BFS 的情況下，它看起來像：
parents = {
'A': NULL,
'B': 'A',
'C': 'A',
'D': 'B',
'E': 'B',
'F': 'C',
'G': 'C'
}
然后，從最后一個節點開始，向后重建路徑：
node = target
path = []
while node:
path.append(node)
node = parents[node]
同樣的方法適用于 DFS 和 Dijkstra
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/442326.html
標籤：c algorithm tree depth-first-search breadth-first-search