爲什麼內存是使用廣度優先搜索時的主要約束

我正在閱讀BFS和DFS，並且我知道BFS使用隊列來存儲節點，而DFS使用堆棧來存儲尚未訪問的節點。但是通過差異，我發現很多網站都提到廣度優先搜索需要更多的內存，因爲它需要隊列來存儲節點。我不明白爲什麼BFS只需要更多的內存，因爲即使DFS使用堆棧來維護節點。任何人都可以讓我知道我是否缺少任何東西？爲什麼內存是使用廣度優先搜索時的主要約束

來源

2014-09-22 kadina

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

BFS和DFS存儲之間的主要區別是，BFS保持隊列它將訪問的節點，而DFS堆棧保留它從根節點到當前節點時所訪問的節點（它將在遍歷當前節點的子節點時返回到這些節點）。

在最壞的情況下，BFS和DFS都會將O（N）個節點存儲在隊列或堆棧中。

從內存使用情況來看，DFS最糟糕的情況是，它將樹中幾乎所有節點都存儲在堆棧中，即當樹看起來像鏈表時（除最後一個節點外，每個節點只有一個子節點）。在這種情況下，堆棧中將有N-1個節點。

對於BFS而言，內存使用情況最糟糕的情況是當您的根節點連接到其他每個節點時，在這種情況下，它將在隊列中存儲N-1個節點 - 與DFS存儲量相同在最壞的情況下在堆棧中。但是如果我們考慮平衡樹（平均情況），DFS將只存儲從根節點到當前節點的路徑（大約是log N個節點），而BFS將存儲隊列，以便平衡當你到達樹的底部時，二叉樹可以大到N/2。

來源

2014-09-22 05:47:03 afenster

當樹是一個鏈表時（每個節點只有一個分支），BFS和DFS是不是等於？對於所有其他情況，DFS使用較少的內存。 – slebetman 2014-09-22 05:55:28

對於鏈接列表，BFS將不會使用與DFS相同的內存量。當DFS堆棧到達最後一個節點時，DFS堆棧將包含除1之外的所有節點，而BFS隊列每次只包含一個節點。 – afenster 2014-09-22 05:56:57

好的。我正在考慮需要通過連接函數調用的值來構建結果的算法。但根據定義，這是DFS。 – slebetman 2014-09-22 06:00:38

那麼，一開始，平衡的樹木往往比它們更高。這是因爲，每當您爲平衡樹添加深度級別時，都會將其容量大致增加一倍。

因此，存儲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

來源

2014-09-22 05:36:50 paxdiablo

謝謝paxdiablo。我現在清楚地瞭解。 – kadina 2014-09-22 05:58:41

爲什麼內存是使用廣度優先搜索時的主要約束

回答

相關問題