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

Question

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

Fra*_* Q. 34 algorithm

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

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

Answer 1

ami*_*mit 57

BFS:

时间复杂度为O(|V|),其中|V|是节点的数量,你需要遍历所有节点.
空间强制性也是O(|V|)如此 - 因为在最坏的情况下,您需要保留队列中的所有顶点.

DFS:

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

(*)请注意,对于树而言,空间复杂度和时间复杂度稍有不同,因为对于一般图形而言,因为您不需要visited为树维护集合|E| = O(|V|),因此该|E|因子实际上是多余的.

@ 500_error对于*tree*,您不需要访问集 - 因为从根到每个节点都有一条路径.访问集的目的是避免多次重新扩展同一节点,但由于存在单个路径 - 不可能发生(在有向图中 - 不需要任何更多数据,在无向图中,需要记住父节点前面的每个节点都是这样的) (5认同)
我不确定这个答案是否正确？据说使用堆栈时 DFS 的空间复杂度为 O(|V|)。然而，堆栈实现仅使用 O(bd) 空间，其中 b 是分支因子，d 是深度。然而，bd != V。另一方面，b^d = V。因此，我认为空间复杂度可以由 O(bd) 更紧密地限制，而不是说 O(|V|)。 (3认同)
@MariaInesParnisari 因为问题是关于一棵树。一棵树有n-1条边，所以遍历所有边和所有顶点与遍历所有顶点是一样的。（请注意，答案明确解释了这一点）。 (2认同)

Answer 2

Luk*_*ens 6

DFS和BFS时间复杂度：O（n）

因为这是树遍历，所以我们必须触摸每个节点，使其为O（n），其中n是树中的节点数。

BFS空间复杂度：O（n）

BFS将必须在队列中至少存储树的整个级别（示例队列实现）。对于一个完美的完全平衡的二叉树，这将是（n / 2 + 1）个节点（最后一层）。最佳情况（在这种情况下），树严重不平衡，并且在每个级别仅包含1个元素，并且空间复杂度为O（1）。最坏的情况是使用无用的N元树存储（n-1）个节点，其中除根节点之外的所有其他节点都位于第二层。

DFS空间复杂度：O（d）

无论实现方式（递归还是迭代），堆栈（隐式或显式）都将包含d个节点，其中d是树的最大深度。对于平衡树，这将是（log n）个节点。DFS的最坏情况将是BFS的最佳情况，而DFS 的最佳情况将是BFS的最坏情况。

它应该是 O(V+E)，您还需要考虑边缘。 (10认同)
@Kyle，如果是正常图表，你是对的。对于二叉树，其 O(N) 因为边数是恒定的 (5认同)
如果您正在寻找树木，这是最好的答案。 (3认同)
所有树（无论是否是二叉树）都有 n-1 条边。O(n + (n-1)) = O(n) (2认同)

Answer 3

小智 5

复杂性有两个主要因素

时间复杂度
空间复杂度

时间复杂度

这是生成节点所需的时间。

在DFS中，所需的时间与深度和分支因子成正比。对于DFS，所需的总时间由-

1 + b + b2 + b3 + ... + bd ~~ bd

因此，时间复杂度= O(bd)

空间复杂度

它是获得解决方案所需的空间或内存量，DFS仅存储它正在追求的当前路径。因此，空间复杂度是深度的线性函数。

所以空间复杂度由 O(d)

归档时间：	13 年，7 月前
查看次数：	64985 次
最近记录：	7 年，6 月前