我知道雙向 BFS 比使用普通 BFS 有很多優勢，因為它理論上可以將發現兩個節點之間的最短路徑的時間和發現一個節點是否可以從另一個節點到達的時間減半。
我也明白只有當我們唯一地定義了兩個節點時，我們才應該使用雙向。
有什么情況我們應該更喜歡普通 BFS 而不是雙向 BFS？
uj5u.com熱心網友回復：
我知道雙向 BFS 由給定的開始和目標節點組成，從開始和目標交替擴展節點層，直到從兩端到達中間的節點。然后將從起點到目標的最短路徑理解為從起點到中間節點的最短路徑，然后是從中間節點到目標的最短路徑。我可以看到，與標準 BFS 方法相比，可能需要擴展的節點更少。然而，
- 實作標準 BFS（sBFS）比實作雙向 BFS（簡稱 bBFS）更容易。簡單通常是好的，因為它更容易編碼并在以后驗證其正確性。
- 如果圖是有向且未加權的，sBFS 保證它會以最少的步長找到從開始到目標的最短路徑；bBFS 不能保證與有向圖一起使用。
- 運行 sBFS 后，您可以重建從開始到所有節點的最短路徑，這些節點最多在目標節點前 1 步（即停止搜索之前）。這本身可能很有價值。運行 bBFS 不會生成這樣的串列。
考慮到這一點，我認為 bBFS 僅適用于非常狹窄的情況（根據圖表，預計它的性能會優于 sBFS），而 sBFS 在更大范圍的場景中既簡單又有用。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/363470.html
上一篇：就地重新排序簡單的二維矩陣