我怎么能记住DFS和BFS使用哪些数据结构？

Question

无论是使用堆栈还是DFS或BFS的队列,我总是混淆.有人可以提供一些关于如何记住哪种算法使用哪种数据结构的直觉？

Answer 1

队列通常被认为是水平的结构,即宽度/宽度可归因于它 - BFS,而

堆栈可视化为垂直结构,因此具有深度 - DFS.

Answer 2

在一张纸上绘制一个小图,并考虑每个实现中处理节点的顺序.在搜索之间,您遇到节点的顺序和处理节点的顺序有何不同？

其中一个使用堆栈(深度优先),另一个使用队列(广度优先)(至少用于非递归实现).

Answer 3

BFS首先探索/处理最近的顶点,然后向外移动远离源.鉴于此,您希望使用一种数据结构,在查询时根据插入的顺序为您提供最旧的元素.在这种情况下,您需要一个队列,因为它是先进先出(FIFO).尽管DFS首先在每个分支上尽可能地进行探索,然后进行包围.为此,堆栈效果更好,因为它是LIFO(后进先出)

Answer 4

我记得把烧烤放在脑海里.烧烤以'B'开头并以'q'结尾,因此BFS - >队列和其余的DFS - >堆栈.

Answer 5

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

DFS --> S --> 堆栈

Answer 6

按字母顺序排列......

.... B(BFS)..... C ...... D(DFS)....

.... Q(队列)...... R ...... S(堆叠)......

Answer 7

BFS使用always queue,Dfs使用Stack数据结构.正如之前的解释所说,DFS正在使用回溯.记住回溯只能通过Stack进行.