我正在閱讀BFS和DFS,並且我知道BFS使用隊列來存儲節點,而DFS使用堆棧來存儲尚未訪問的節點。但是通過差異,我發現很多網站都提到廣度優先搜索需要更多的內存,因爲它需要隊列來存儲節點。我不明白爲什麼BFS只需要更多的內存,因爲即使DFS使用堆棧來維護節點。任何人都可以讓我知道我是否缺少任何東西?爲什麼內存是使用廣度優先搜索時的主要約束
0
A
回答
1
BFS和DFS存儲之間的主要區別是,BFS保持隊列它將訪問的節點,而DFS堆棧保留它從根節點到當前節點時所訪問的節點(它將在遍歷當前節點的子節點時返回到這些節點)。
在最壞的情況下,BFS和DFS都會將O(N)個節點存儲在隊列或堆棧中。
從內存使用情況來看,DFS最糟糕的情況是,它將樹中幾乎所有節點都存儲在堆棧中,即當樹看起來像鏈表時(除最後一個節點外,每個節點只有一個子節點) 。在這種情況下,堆棧中將有N-1個節點。
對於BFS而言,內存使用情況最糟糕的情況是當您的根節點連接到其他每個節點時,在這種情況下,它將在隊列中存儲N-1個節點 - 與DFS存儲量相同在最壞的情況下在堆棧中。但是如果我們考慮平衡樹(平均情況),DFS將只存儲從根節點到當前節點的路徑(大約是log N個節點),而BFS將存儲隊列,以便平衡當你到達樹的底部時,二叉樹可以大到N/2。
4
那麼,一開始,平衡的樹木往往比它們更高。這是因爲,每當您爲平衡樹添加深度級別時,都會將其容量大致增加一倍。
因此,存儲16,383項,您的寬度在樹的底部是8,192,但你的深度只有14:
Level 1: 1
2: 2-3
3: 4-7
4: 8-15
5: 16-31
6: 32-63
7: 64-127
8: 128-255
9: 256-511
10: 512-1023
11: 1024-2047
12: 2048-4095
13: 4096-8191
14: 8192-16383
+0
謝謝paxdiablo。我現在清楚地瞭解。 – kadina 2014-09-22 05:58:41
相關問題
- 1. 如何理解廣度優先搜索的內存問題分支和約束
- 2. 將廣度優先搜索轉換爲深度優先使用Java搜索
- 3. 廣度優先搜索 - Java
- 4. 廣度優先搜索
- 5. 廣度優先搜索java.lang.NullPointerException
- 6. Java廣度優先搜索?
- 7. 實現A * - 搜索作爲廣度優先搜索/深度優先搜索
- 8. 廣度優先搜索使用陣列
- 9. 廣度優先搜索使用Javascript
- 10. 廣度優先搜索和深度優先搜索
- 11. 深度優先搜索和廣度優先搜索瞭解
- 12. 爲什麼prolog統一深度優先搜索而不是廣度優先搜索?
- 13. 優先深度優先搜索廣度優先搜索或反之亦然
- 14. 廣度優先搜索/深度優先搜索還是定向圖?
- 15. 廣度優先搜索不起作用
- 16. 深度或廣度優先搜索?
- 17. 廣度優先與深度優先搜索的輸入/輸出
- 18. F#中的廣度優先搜索(BFS)
- 19. 廣度優先或深度優先搜索
- 20. 功能廣度優先搜索
- 21. BFS代碼(廣度優先搜索)
- 22. 並行廣度優先搜索
- 23. 如何實現廣度優先搜索?
- 24. 廣度優先搜索 - 標準Python庫
- 25. 最短路徑 - 廣度優先搜索
- 26. 廣度優先搜索解決難題
- 27. 廣度優先搜索練習 - AI
- 28. 廣度優先搜索錯誤輸出
- 29. 廣度優先搜索算法
- 30. 廣度優先搜索問題C++
http://www.quora.com/Why-is-DFS-usually-more-space-efficient-than-BFS – Skynet 2014-09-22 05:34:04
看看這個所以:http://stackoverflow.com/questions/20429310/why- is-dfs-depth-first-search-claim-to-space-efficient – 2014-09-22 05:34:27