廣度優先或深度優先搜索

Question

我知道這個算法是如何工作的，但不能決定何時使用哪種算法？

是否有一些指導方針，其中一個更好地執行比其他或任何考慮？

非常感謝。

Answer 1

如果你想找到一個最短步數的解決方案，或者如果你的樹有無限高度（或非常大），你應該首先使用寬度。

如果您有一棵有限樹並且想要使用最小的內存量遍歷所有可能的解決方案，那麼您應該首先使用深度。

如果你正在尋找最好的國際象棋移動發揮你可以使用iterative deepening這是兩者的組合。

IDDFS結合了深度優先搜索的空間效率和廣度優先搜索的完整性（當分支因子是有限的）。

Answer 2

BFS是在圖中有一些有意義的「自然分層」的情況下通常是有用的（例如，更靠近節點代表「接近」的結果），你的目標的結果很可能是更靠近起點或起點積分「搜索便宜」。

當你想找到最短路徑時，BFS是一個很自然的選擇。

如果你的圖是無限的或者是在語法上產生的，你可能想在冒險之前搜索更接近的圖層，因爲在到達更近的節點之前探索遠程節點的代價是過高的。

如果由於內存/磁盤/局域性問題訪問更多遠程節點會更加昂貴，那麼BFS可能會再好一些。

Answer 3

使用哪種方法通常取決於應用（即爲什麼必須搜索圖） - 例如，拓撲排序需要深度優先搜索，而用於查找最大流量的Ford-Fulkerson算法需要廣度優先搜索。

Answer 4

如果您遍歷樹，深度優先將使用與其深度成比例的內存。如果樹合理平衡（或者對其深度有其他限制），則可以使用遞歸深度優先遍歷。

但是，不要這樣做遍歷一般圖;它可能會導致堆棧溢出。對於無界樹或一般圖，您將需要某種輔助存儲，可以擴展到與輸入節點數成比例的大小。在這種情況下，寬度優先遍歷簡單方便。

如果您的問題提供了選擇一個節點而不是另一個節點的理由，您可以考慮使用優先級隊列，而不是棧（深度優先）或FIFO（寬度優先）。優先級隊列將花費O（log K）時間（其中K是不同優先級的當前數量）來查找每個步驟中的最佳節點，但優化可能是值得的。