什么是广度第一和深度优先遍历树的时间和空间复杂？ [英] What is the time and space complexity of a breadth first and depth first tree traversal?

问题描述

有人可以用一​​个例子来说明我们如何计算这两种遍历方法的时间和空间复杂？

Can someone explain with an example how we can calculate the time and space complexity of both these traversal methods?

另外，如何递归的解决方案，以深度优先遍历影响的时间和空间复杂？

Also, how does recursive solution to depth first traversal affect the time and space complexity?

推荐答案

BFS：

时间复杂度为 O（| V |），其中 | V | 是节点的数目，则需要遍历所有节点。
空间complecity是 O（| V |）。以及 - 因为在最坏的情况下，你需要保存所有的顶点队列中的

Time complexity is O(|V|) where |V| is the number of nodes,you need to traverse all nodes.
Space complecity is O(|V|) as well - since at worst case you need to hold all vertices in the queue.

DFS：

时间复杂度又是 O（| V |），您需要遍历所有节点。
空间的复杂性 - 依赖于实现，递归的实现可以有一个 0（H）空间复杂度[最坏的情况下]，其中 ^ h 是树的最大深度。
使用迭代解决方案堆栈实际上是一样的BFS，只是用一堆而不是一个队列 - 让你同时获得 O（| V |）时间和空间复杂度。

Time complexity is again O(|V|), you need to traverse all nodes.
Space complexity - depends on the implementation, a recursive implementation can have a O(h) space complexity [worst case], where h is the maximal depth of your tree.
Using an iterative solution with a stack is actually the same as BFS, just using a stack instead of a queue - so you get both O(|V|) time and space complexity.

（*）请注意，空间复杂度和时间复杂度是有点不同的一棵树那么对于一般图becase的你并不需要维持一个访问设置一棵树， | E | = O（| V |），所以 | E |。的因素其实是多余的。

(*) Note that the space complexity and time complexity is a bit different for a tree then for a general graphs becase you do not need to maintain a visited set for a tree, and |E| = O(|V|), so the |E| factor is actually redundant.

这篇关于什么是广度第一和深度优先遍历树的时间和空间复杂？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！