如何记住 DFS 和 BFS 使用哪些数据结构？
我总是混淆是使用堆栈还是队列来进行 DFS 或 BFS。有人可以提供一些关于如何记住哪种算法使用哪种数据结构的直觉吗？
I always mix up whether I use a stack or a queue for DFS or BFS. Can someone please provide some intuition about how to remember which algorithm uses which data structure?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（17）
队列一般可以认为是水平结构，即宽度/宽度可以归因于它 - BFS，而
Stack被可视化为垂直结构，因此具有深度 - DFS。
Queue can be generally thought as horizontal in structure i.e, breadth/width can be attributed to it - BFS, whereas
Stack is visualized as a vertical structure and hence has depth - DFS.
在一张纸上画一个小图，并思考每个实现中处理节点的顺序。在搜索之间遇到节点的顺序和处理节点的顺序有何不同？
其中一个使用堆栈（深度优先），另一个使用队列（广度优先）（至少对于非递归实现）。
Draw a small graph on a piece of paper and think about the order in which nodes are processed in each implementation. How does the order in which you encounter the nodes and the order in which you process the nodes differ between the searches?
One of them uses a stack (depth-first) and the other uses a queue (breadth-first) (for non-recursive implementations, at least).
我把烧烤记在了心里。烧烤以“B”开始，以“q”这样的声音结束，因此 BFS ->队列和剩余的DFS ->堆。
I remember it by keeping Barbecue in my mind. Barbecue starts with a 'B' and ends with a sound like 'q' hence BFS -> Queue and the remaining ones DFS -> stack.
BFS 首先探索/处理最近的顶点，然后向外移动远离源。鉴于此，您希望使用一种数据结构，在查询时根据插入的顺序为您提供最旧的元素。在这种情况下您需要队列，因为它是先进先出（FIFO）的。
而 DFS 首先沿着每个分支探索尽可能远的距离，然后再进行分支探索。为此，堆栈效果更好，因为它是 LIFO（后进先出）
BFS explores/processes the closest vertices first and then moves outwards away from the source. Given this, you want to use a data structure that when queried gives you the oldest element, based on the order they were inserted. A queue is what you need in this case since it is first-in-first-out(FIFO).
Whereas a DFS explores as far as possible along each branch first and then bracktracks. For this, a stack works better since it is LIFO(last-in-first-out)
按字母顺序排列...
.... B(BFS)...C...D (DFS)...
.... Q(Queue)...R.. ....S（堆栈）...
Take it in Alphabetical order...
.... B(BFS).....C......D (DFS)....
.... Q(Queue)...R......S (Stack)...
BFS——> B——>烧烤--> 队列
DFS --> S——>堆
BFS --> B --> Barbecue --> Queue
DFS --> S --> Stack
BFS使用always队列，Dfs使用Stack数据结构。正如前面关于 DFS 的解释所说，它使用回溯。请记住，回溯只能通过堆栈进行。
BFS uses always queue, Dfs uses Stack data structure. As the earlier explanation tell about DFS is using backtracking. Remember backtracking can proceed only by Stack.
什么都不记得了。
假设用于搜索的数据结构是X：
广度优先=之前输入X的节点，必须是首先在树上生成：X 是一个队列。
深度优先 = 稍后输入 X 的节点必须生成首先在树上：X是一个栈。
简单来说：栈就是后进先出，也就是DFS。队列是先进先出的，也就是BFS。
Don't remember anything.
Assuming the data structure used for the search is X:
Breadth First = Nodes entered X earlier, have to be generated on the tree first: X is a queue.
Depth First = Nodes entered X later, must be generated on the tree first: X is a stack.
In brief: Stack is Last-In-First-Out, which is DFS. Queue is First-In-First-Out, which is BFS.
参考它们的结构
Refer to their structure
深度优先搜索使用
Stack来记住当到达死胡同时应该去哪里。The depth-first search uses a
Stackto remember where it should go when it reaches a dead end.堆栈（后进先出，LIFO）。对于DFS，我们尽可能从根节点检索到最远的节点，这与后进先出的思想相同。
队列（先进先出，FIFO）。对于BFS来说，我们一层一层地检索，访问上层节点后，再访问底层节点，这和FIFO的思想是一样的。
Stack (Last In First Out, LIFO). For DFS, we retrieve it from root to the farthest node as much as possible, this is the same idea as LIFO.
Queue (First In First Out, FIFO). For BFS, we retrieve it one level by one leve, after we visit upper level of the node, we visit bottom level of node, this is the same idea as FIFO.
一个更容易记住的方法，特别是对于年轻的学生来说，是使用类似的缩写：
BFS =>男朋友在排队（显然是为了受欢迎的女士）。
DFS 则不然（堆栈）。
An easier way to remember, especially for young students, is to use similar acronym:
BFS => Boy FriendS in queue (for popular ladies apparently).
DFS is otherwise (stack).
如果您将“q”符号（如 queue 中的）旋转 180 度，您将得到“b”（如 bfs 中的）。
否则，这就是堆栈和 dfs。
if you visually rotate 'q' symbol (as in queue) 180 degrees you will get a 'b' (as in bfs).
Otherwise this is stack and dfs.
我想分享这个答案：
https://stackoverflow.com/a/20429574/3221630
采用 BFS 并用堆栈替换队列，重现同样的DFS访问顺序，它比实际的DFS算法使用更多的空间。
I would like to share this answer:
https://stackoverflow.com/a/20429574/3221630
Taking BFS and replacing a the queue with a stack, reproduces the same visiting order of DFS, it uses more space than the actual DFS algorithm.
您可以通过制作首字母缩略词
BQDS
来记住美丽的女王有罪。
在印地语中，
बहुरानी क्यु दर्द सहा
You can remember by making an acronym
BQDS
Beautiful Queen has Done Sins.
In Hindi,
बहुरानी क्यु दर्द सहा
这是一个需要记住的简单类比。在 BFS 中，您一次只能进入一层，但在 DFS 中，您会在访问其他层之前尽可能向左深入。基本上就是堆积一大堆东西，然后一一分析，所以如果这是STACK，那么另一个就是队列。
记住“堆积”、“堆积”，尽可能大。 （DFS）。
Here is a simple analogy to remember. In a BFS, you are going one level at a time but in DFS you are going as deep as possible to the left before visiting others. Basically stacking up a big pile of stuff, then analyze them one by one, so if this is STACK, then the other one is queue.
Remember as "piling up", "stacking up", big as possible. (DFS).
堆栈 = 堆栈煎饼。一堆煎饼掉了下来。很深。深度优先。
Queue = 队列是（人的）一条线。线路变宽。宽是广度第一。
Stack = Stack of Pancakes. A stack of pancakes goes down. It's deep. Depth First.
Queue = A Queue is a Line (of people). Lines go wide. Wide is Breadth First.