1. 首頁
  2. 問答
  3. 如何記住DFS和BFS使用的數據結構？

如何記住DFS和BFS使用的數據結構？

2010-10-14 38 views

回答

13

在一張紙上繪製一個小圖，並考慮在每個實現中處理節點的順序。在搜索中，您遇到節點的順序和處理節點的順序如何不同？

其中一個使用堆棧（深度優先），另一個使用隊列（寬度優先）（對於非遞歸實現至少）。

來源

2010-10-14 00:22:47

23

BFS首先探索/處理最近的頂點，然後向外移動離開源。鑑於此，您希望使用數據結構，在查詢時根據它們插入的順序給出最老的元素。在這種情況下，隊列就是你需要的，因爲它是先進先出（FIFO）。 儘管DFS儘可能沿着每個分支探索，然後沿着分支進行探索。爲此，堆棧工作得更好，因爲它是LIFO（後進先出）

來源

2011-10-20 08:56:49

4

BFS使用始終隊列，Dfs使用堆棧數據結構。正如前面的解釋所述，DFS正在使用回溯。記住回溯只能通過堆棧進行。

來源

2013-03-04 09:30:20 ashutosh

2

BFS;寬度=>隊列

的DFS;深度=>堆棧

參考它們的結構

來源

2013-03-24 06:16:47 Subrato

18

我通過保持烤肉在我的腦海裏記住它。燒烤以'B'開始，以'q'結尾，因此BFS - > Queue和剩餘的DFS - >堆疊。

來源

2014-09-28 09:51:51 kawadhiya21

+0

良好的觀察:) – RBT 2017-04-19 01:17:39

28

隊列通常可以認爲是在結構上即水平，廣度/寬度可以歸因於它 - BFS，而

堆棧可視化爲垂直結構因此具有深度-DFS。

來源

2015-09-24 05:23:19

+0

對於新的學習者來說是一個很好的視覺線索。 +1。 – displayName 2017-11-10 22:24:36

1

深度優先搜索使用Stack來記住它在到達死衚衕時應該到達的位置。

DFSS

來源

2016-05-06 08:36:24

3

把它按字母順序排列...

.... B（BFS）...... C ...... d（DFS）。 ...

.... Q（隊列）... [R ...... S（棧）...

來源

2016-05-17 10:59:39

1

  1. 堆疊（後進先出，LIFO）。對於DFS，我們儘可能從根節點到最遠節點檢索它，這與LIFO的想法是一樣的。

  2. 隊列（先進先出FIFO）。對於BFS，我們一層一層地檢索它，在訪問節點的上層之後，我們訪問節點的底層，這與FIFO相同。

來源

2017-07-03 13:28:55 EntryLeveDeveloper

相關問題

 相關問題