有人可以用一个例子来解释我们如何计算这两种遍历方法的时间和空间复杂度？
此外，深度优先遍历的递归解决方案如何影响时间和空间复杂度？
BFS:
时间复杂度为 O(|V|) ，其中 |V| 是节点数，需要遍历所有节点 .空间complecity也是 O(|V|) - 因为在最坏的情况下你需要保持队列中的所有顶点 .
O(|V|)
|V|
DFS:
时间复杂度又是 O(|V|) ，您需要遍历所有节点 .空间复杂度 - 取决于实现，递归实现可能具有 O(h) 空间复杂性[最坏情况]，其中 h 是树的最大深度 .使用带有堆栈的迭代解决方案实际上与BFS相同，只是使用堆栈而不是队列 - 因此您同时获得时间和空间复杂性 .
O(h)
h
（*）请注意，对于树而言，空间复杂度和时间复杂度稍有不同，因此对于一般图形而言，因为您不需要为树维护 visited ，而 |E| = O(|V|) 因此实际上是多余的 .
visited
|E| = O(|V|)
复杂性有两个主要因素
时间复杂性
空间复杂性
它是生成节点所需的时间量 .
在DFS中，所需的时间量与深度和分支因子成比例 . 对于DFS，所需的总时间由下列人员给出：
1 b b2 b3 ... bd ~~ bd
因此时间复杂度= O(bd)
O(bd)
获取解决方案所需的空间或内存量DFS仅存储它所追求的当前路径 . 因此，空间复杂度是深度的线性函数 .
所以空间复杂性由 O(d) 给出
O(d)
因为这是树 traversal ，我们必须触摸每个节点，使这个O（n），其中n是树中的节点数 .
BFS必须至少存储队列中整个树的级别（示例queue implementation） . 使用完美的完全 balancer 二叉树，这将是（n / 2 1）个节点（最后一个级别） . 最佳情况（在此上下文中），树严重不 balancer ，每个级别只包含1个元素，空间复杂度为O（1） . 最坏的情况是存储（n-1）个节点，其中有一个相当无用的N-ary树，其中除根节点之外的所有节点都位于第二级 .
无论实现（递归还是迭代），堆栈（隐式或显式）都将包含d个节点，其中d是树的最大深度 . 使用 balancer 树，这将是（log n）节点 . 最糟糕的DFS案例将是BFS的最佳案例，而DFS的最佳案例将是BFS的最坏情况 .
3 回答
BFS:
时间复杂度为
O(|V|)，其中|V|是节点数，需要遍历所有节点 .空间complecity也是
O(|V|)- 因为在最坏的情况下你需要保持队列中的所有顶点 .DFS:
时间复杂度又是
O(|V|)，您需要遍历所有节点 .空间复杂度 - 取决于实现，递归实现可能具有
O(h)空间复杂性[最坏情况]，其中h是树的最大深度 .使用带有堆栈的迭代解决方案实际上与BFS相同，只是使用堆栈而不是队列 - 因此您同时获得时间和空间复杂性 .
（*）请注意，对于树而言，空间复杂度和时间复杂度稍有不同，因此对于一般图形而言，因为您不需要为树维护
visited，而|E| = O(|V|)因此实际上是多余的 .复杂性有两个主要因素
时间复杂性
空间复杂性
时间复杂性
它是生成节点所需的时间量 .
在DFS中，所需的时间量与深度和分支因子成比例 . 对于DFS，所需的总时间由下列人员给出：
1 b b2 b3 ... bd ~~ bd
因此时间复杂度=
O(bd)空间复杂性
获取解决方案所需的空间或内存量DFS仅存储它所追求的当前路径 . 因此，空间复杂度是深度的线性函数 .
所以空间复杂性由
O(d)给出DFS和BFS时间复杂度：O（n）
因为这是树 traversal ，我们必须触摸每个节点，使这个O（n），其中n是树中的节点数 .
BFS空间复杂度：O（n）
BFS必须至少存储队列中整个树的级别（示例queue implementation） . 使用完美的完全 balancer 二叉树，这将是（n / 2 1）个节点（最后一个级别） . 最佳情况（在此上下文中），树严重不 balancer ，每个级别只包含1个元素，空间复杂度为O（1） . 最坏的情况是存储（n-1）个节点，其中有一个相当无用的N-ary树，其中除根节点之外的所有节点都位于第二级 .
DFS空间复杂度：O（d）
无论实现（递归还是迭代），堆栈（隐式或显式）都将包含d个节点，其中d是树的最大深度 . 使用 balancer 树，这将是（log n）节点 . 最糟糕的DFS案例将是BFS的最佳案例，而DFS的最佳案例将是BFS的最坏情况 .