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

cap*_*ver 26 queue stack breadth-first-search depth-first-search

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

小智 76

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

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

  • 这应该是公认的答案。太直观了! (4认同)

Jam*_*lis 27

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

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


小智 26

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


kaw*_*a21 26

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

  • 哈哈哈OMG,当我偶然遇到这个问题时,我没有遇到OP的问题,但是在阅读了这个答案之后,我绝对不会忘记:D (2认同)

Yan*_*uan 10

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

DFS --> S --> 堆栈


小智 6

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

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

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


小智 5

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