algorithm - 广度优先和深度优先树遍历的时间和空间复杂度是多少？

Question

有人可以举例说明我们如何计算这两种遍历方法的时间和空间复杂度吗？

另外，深度优先遍历的递归解对时空复杂度有什么影响？

Answer 1

BFS:

时间复杂度为O(|V|)，其中|V|为节点数。您需要遍历所有节点。
空间复杂度也是 O(|V|) - 因为在最坏的情况下，您需要将所有顶点保存在队列中。

DFS:

时间复杂度又是O(|V|)，需要遍历所有节点。
空间复杂度 - 取决于实现，递归实现可以具有 O(h) 空间复杂度 [最坏情况]，其中 h 是最大深度你的树。
使用堆栈的迭代解决方案实际上与 BFS 相同，只是使用堆栈而不是队列 - 所以您同时获得 O(|V|) 时间和空间复杂度。

(*) 请注意，树的空间复杂度和时间复杂度与一般图略有不同，因为您不需要为树维护 visited 集，并且 |E| = O(|V|)，所以 |E| 因素实际上是多余的。