logo标签列表

我该如何记住深度优先搜索和广度优先搜索使用哪些数据结构？

stackqueuedepth-first-searchbreadth-first-search
49

我经常混淆DFS或BFS使用堆栈(stack)还是队列(queue)。请问有人可以提供一些直觉来记住哪种算法使用哪种数据结构吗？

16个回答
165

队列（Queue）可以被普遍看作是水平的结构，即可以将其归属于广度优先搜索（BFS），因为它具有宽度/横向。

栈（Stack）被视为垂直的结构，因此具有深度，可以归属于深度优先搜索（DFS）。

4
这应该是被接受的答案。太直观了！ - disklosr
43

在一张纸上画一个小图，思考每种实现中处理节点的顺序。你遇到节点的顺序和处理节点的顺序在不同搜索之间有何区别？

其中一种使用栈（深度优先），另一种使用队列（广度优先）（至少对于非递归实现而言）。

41

我记得它是通过将烧烤牢记在我的脑海中。 烧烤以“B”开头，以类似于“q”的声音结束，因此BFS->队列，其余的DFS->堆栈。

1
很好的观察 :) - RBT
1
谷歌似乎喜欢这个答案。如果您搜索此问题，谷歌会提取出这个答案。因此，这里为此点赞。 - tryurbest
2
哈哈哈，我在看到这个问题时没有遇到OP的问题，但是在阅读了这个答案后，我绝不会忘记它 :D - M-J
27

BFS先探索/处理最近的顶点，然后向外从源点移动。因此，您需要使用一种数据结构，当查询时，该数据结构按照它们被插入的顺序给出最旧的元素。在这种情况下，您需要使用队列，因为它是先进先出（FIFO）的。

而DFS首先沿着每个分支尽可能远地探索，然后回溯。对于这个问题，栈更好，因为它是后进先出（LIFO）的。

11

按照字母顺序来看……

……B（广度优先搜索）……C……D（深度优先搜索）……

……Q（队列）……R……S（栈）……

10
BFS使用队列，DFS使用堆栈数据结构。正如之前的解释所述，DFS使用回溯。请记住，只有通过堆栈才能进行回溯。
10

BFS --> B --> 烧烤串 --> 队列

DFS --> D --> 栈

:D :D :D :D :D :D :D - Yaman
4

不记得任何事情。

假设用于搜索的数据结构为X：

广度优先 = 先进入X的节点必须首先在树上生成：X是队列。

深度优先 = 后进入X的节点必须首先在树上生成：X是堆栈。

简而言之：堆栈是后进先出，即DFS。队列是先进先出，即BFS。

3
引用他们的结构：
广度优先搜索；宽度 => 队列
深度优先搜索；深度 => 栈
2
深度优先搜索使用一个堆栈来记住当它到达死路时应该去哪里。

DFSS

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接