我总是混淆是否使用堆栈或队列进行 DFS 或 BFS。有人可以提供一些关于如何记住哪种算法使用哪种数据结构的直觉吗？
问问题
80720 次
15 回答
142
队列在结构上通常可以被认为是水平的，即宽度/宽度可以归因于它 - BFS，而
堆栈被可视化为垂直结构，因此具有深度-DFS 。
于 2015-09-24T05:23:19.907 回答
41
在一张纸上画一个小图，并考虑在每个实现中处理节点的顺序。遇到节点的顺序和处理节点的顺序在搜索之间有何不同？
其中一个使用堆栈（深度优先），另一个使用队列（宽度优先）（至少对于非递归实现）。
于 2010-10-14T00:22:47.327 回答
39
我把烧烤记在心里。烧烤以“B”开头，以“q”之类的声音结束，因此 BFS -> Queue 和其余的 DFS -> stack。
于 2014-09-28T09:51:51.300 回答
27
BFS 首先探索/处理最近的顶点，然后从源向外移动。鉴于此，您希望使用一种数据结构，在查询时根据插入的顺序为您提供最旧的元素。在这种情况下，您需要一个队列，因为它是先进先出（FIFO）。而 DFS 首先沿着每个分支尽可能地探索，然后再探索。为此，堆栈效果更好，因为它是 LIFO（后进先出）
于 2011-10-20T08:56:49.623 回答
10
BFS 使用 always queue，Dfs 使用 Stack 数据结构。正如前面的解释所说，DFS 正在使用回溯。请记住，回溯只能通过 Stack 进行。
于 2013-03-04T09:30:20.253 回答
10
把它按字母顺序...
.... B（BFS）......C......D（DFS）......
.... Q（队列）...R......S（堆栈）...
于 2016-05-17T10:59:39.507 回答
6
BFS --> B --> 烧烤 -->队列
DFS --> S --> 堆栈
于 2020-12-04T09:42:12.117 回答
4
什么都不记得。
假设用于搜索的数据结构是X：
广度优先= 较早进入X的节点，必须首先在树上生成： X 是一个队列。
深度优先= 稍后进入X的节点，必须首先在树上生成： X 是一个堆栈。
简而言之：堆栈是后进先出的，也就是DFS。队列是先进先出的，也就是BFS。
于 2018-11-25T10:58:59.163 回答
3
Bfs;宽度=>队列
Dfs;深度=>堆栈
参考它们的结构
于 2013-03-24T06:16:47.817 回答
2
深度优先搜索使用 aStack来记住当它到达死胡同时它应该去哪里。
DFSS
于 2016-05-06T08:36:24.163 回答
1
一种更容易记住的方法，尤其是对于年轻学生来说，是使用类似的首字母缩略词：
BFS => Boy FriendS 在队列中（显然是受欢迎的女士）。
否则 DFS 是（堆栈）。
于 2018-05-27T06:42:38.617 回答
1
堆栈（后进先出，LIFO）。对于 DFS，我们尽可能从根到最远的节点检索它，这和 LIFO 的想法是一样的。
队列（先进先出，FIFO）。对于BFS，我们一层一层的取回，访问上一层节点后，再访问底层节点，这和FIFO的思路是一样的。
于 2017-07-03T13:28:55.400 回答
0
于 2018-07-28T15:30:28.390 回答
0
这是一个需要记住的简单类比。在 BFS 中，您一次走一个级别，但在 DFS 中，您在访问其他人之前尽可能向左走。基本上是堆了一大堆东西，然后一个一个地分析，所以如果这是STACK，那么另一个是队列。
记住“堆积”，“堆积”，尽可能大。(DFS)。
于 2020-11-12T20:55:18.223 回答
0
我想分享这个答案： https ://stackoverflow.com/a/20429574/3221630
采用 BFS 并用堆栈替换队列，再现了 DFS 的相同访问顺序，它比实际的 DFS 算法使用更多的空间。
于 2017-04-30T02:05:02.380 回答