相关疑难解决方法(0)

遍历树/图时,广度优先和深度之间的区别首先是什么？任何编码或伪代码示例都会很棒.

如果给出一个图形问题,我们怎么知道我们是否需要使用bfs或dfs算法？或者我们何时使用dfs算法或bfs算法.一个人与另一个人有什么区别和优势？

在我正在考虑的算法课程中,据说深度优先搜索(DFS)比广度优先搜索(BFS)更具空间效率.

这是为什么？

虽然它们基本上都在做同样的事情,但在DFS中我们正在堆叠当前节点的后继者,而在BFS中我们将后续队列入队.

我在网上找不到这个问题的答案,而在其他类似问题的答案中,似乎DFS的一个优点就是它使用的内存比DFS少.

对我而言,这似乎与我的期望相反.BFS只需存储它访问的最后一个节点.例如,如果我们在下面的树中搜索数字7:

它会搜索值为8的节点,然后是3,10,1,6,14,4,然后是最终的7.对于DFS,它将搜索值为8的节点,然后是3,1,6,4,最后是7 .

如果每个节点都存储在内存中,并且有关于其值,子节点以及它在树中的位置的信息,则BFS程序只需要存储有关其访问的最后一个节点的位置的信息,然后它就可以检查树,找到树中的下一个节点.DFS程序必须存储它所在的最后一个节点,以及它已经访问过的所有节点,因此它不会再次检查它们,只是循环遍历从第二代到最后一代节点之一的所有叶节点.

那么为什么BFS实际上使用更少的内存呢？

我现在正在使用D3.js树布局创建组织结构图.组织结构图将由登录用户打开,并且要求显示默认情况下打开到用户节点的组织结构图.

例如,如果登录用户为"n",则组织结构图为:

        j   m
       /   /
  b - e - k
 /
a - d - l - n
 \
  c- f - h
      \ 
       i

用户将看到:

a - d - l - n

因此,问题陈述是将组织结构图扩展到节点id/name是登录用户的特定节点.

欢迎任何帮助.

我知道 DFS 对某些问题有好处，而 BFS 对其他一些问题有好处，但如果可以使用 DFS 解决某些问题，是否可以用 BFS 解决（可能不太理想）（反之亦然）？有证据吗？谢谢！