logo标签列表

BFS：递归与迭代的区别

recursiontreeiterationbinary-treebreadth-first-search
4
有没有递归编写BFS树遍历算法的优势？对我来说，迭代实现是更好的选择，因为它可以在简单循环中实现：
  1. 将根节点入队
  2. 出队节点并检查
  3. 将其子节点入队
  4. 返回步骤2
递归有什么优势吗？它似乎更加复杂而没有任何优点。
提前感谢您的帮助...
3
“process is not the same as procedure” 的意思是“过程（process）并不等同于过程的实现方法（procedure）”，递归程序不一定会产生递归过程。 - Mulan
3
你似乎已经回答了自己的问题：“这似乎更复杂且没有优势”。我也看不出有任何好处，并且我见过的所有实现都是基于队列的。 - Some Guy
你怎么才能用递归来实现它？递归只是场景后面的堆栈，而BFS则是队列。我认为这是不可能的，除非有一些巫术。 - Shihab Shahriar Khan
1个回答
0

在考虑算法时，我们主要考虑时间复杂度和空间复杂度。 迭代广度优先搜索的时间复杂度为O（|V|+|E|），其中|V|是图中顶点的数量，|E|是边的数量。递归广度优先搜索也是如此。 而迭代广度优先搜索的空间复杂度为O（|V|）。递归广度优先搜索也是如此。

从时间复杂度和空间复杂度的角度来看，这两种算法之间没有区别。由于迭代广度优先搜索易于理解，因此人们更喜欢使用迭代广度优先搜索。

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